13
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – DarthGizka
    Commented Nov 10, 2014 at 14:54
  • $\begingroup$ The OEIS entry explicitly states a(12) > 2^64. $\endgroup$ Commented Nov 12, 2014 at 13:38

1 Answer 1

12
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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? $\endgroup$ Commented Jul 12, 2012 at 0:49
  • 1
    $\begingroup$ @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. $\endgroup$
    – Charles
    Commented Jul 23, 2012 at 17:37
  • $\begingroup$ 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. $\endgroup$ Commented Jul 30, 2014 at 8:50
  • 2
    $\begingroup$ The conventions used by the author of miller-rabin.appspot.com are described in priv.ckp.pl/wizykowski/sprp.pdf , though not particularly clearly. You are supposed to test all bases not divisible by $n$. Note that the definition of base-$a$ strong pseudoprimes really only makes good sense for $(n,a)=1$. The commonly presented randomized algorithm, restricting the bases to $1<a<n$, exploits the unrelated fact that any common factor of $n$ and $a$ will make $n$ composite, however this is not literally true for $a\ge n$, one must exclude multiples of $n$. $\endgroup$ Commented Jul 30, 2014 at 10:48
  • 3
    $\begingroup$ Is there a paper or some other verification for Jim Sinclair's 7-base set? Google only turned up nothing beyond the nebulous statement on the above-linked page ("at least 2^64"); was the set tested exhaustively up to 2^64-1? $\endgroup$
    – DarthGizka
    Commented Nov 10, 2014 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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