I know that no number less than 64 bits will fail the MillerRabin tests for all of the first 12 primes. That is, those 12 tests will provide a fully deterministic primality test for all 64 bit numbers. (See http://oeis.org/A014233). I also know that for 32 bit numbers, it suffices to apply the MillerRabin tests for the three bases 2, 7 and 61. (See http://primes.utm.edu/prove/merged.html). Is there a very small list of possible bases (other than the first 12 primes), which will provide a fully deterministic test for 64 bit primes?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
According to http://millerrabin.appspot.com/, the 7element set {2, 325, 9375, 28178, 450775, 9780504, 1795265022} works for 64bit integers. 

