Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I know that no number less than 64 bits will fail the Miller-Rabin 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 Miller-Rabin 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?

share|improve this question
    
Is there a particular reason to believe that the first 12 primes are sufficient to cover 64-bit primes? From the OEIS list we can only deduce that the 11ish set fails at 61.7 bits; the 12ish set might fail very soon after for all we know –  DarthGizka Nov 10 at 14:54
    
The OEIS entry explicitly states a(12) > 2^64. –  Emil Jeřábek Nov 12 at 13:38

1 Answer 1

up vote 8 down vote accepted

According to http://miller-rabin.appspot.com/, the 7-element set {2, 325, 9375, 28178, 450775, 9780504, 1795265022} works for 64-bit integers.

share|improve this answer
    
Thanks very much - that website (of which I was unaware) answers my question very nicely. I now need to search for some references: I wonder whether Jim Sinclair's 7-base solution is optimal? –  Alasdair McAndrew Jul 12 '12 at 0:49
1  
@Alasdair McAndrew: Surely not. If all you need is 2^64 it should be not only possible but tractable to find a 6-base solution. It's not impossible that a 5-base solution exists but finding one seems extremely unlikely without advances in the theory. –  Charles Jul 23 '12 at 17:37
    
How does this even work? I'm seeing failures when trying this set, because the numbers 4033 and 4681 are both pseudoprimes to base 2 and 325. –  Todd Lehman Jul 30 at 8:50
    
So? They are not pseudoprimes to base 9375. –  Emil Jeřábek Jul 30 at 9:04
    
Right, but aren't you supposed to only test those bases which are less than n? In other words, for n=4033, only the bases 2 and 325 would be tested, no? If that's not the case, and you're supposed to test all the bases regardless of how they compare with n, then how does it not think 5 is composite when 325 ≡ 0 (mod 5)? I thought it was fine if a base produced a strong pseudoprime (e.g., 325 producing 9 and 27), but to miss a prime is a big problem, right? [Forgive me if this question is ridiculous; I'm just learning M-W this week.] –  Todd Lehman Jul 30 at 10:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.