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?
$\begingroup$
$\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$– DarthGizkaCommented Nov 10, 2014 at 14:54
-
$\begingroup$ The OEIS entry explicitly states a(12) > 2^64. $\endgroup$– Emil JeřábekCommented Nov 12, 2014 at 13:38
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
According to http://miller-rabin.appspot.com/, the 7-element set {2, 325, 9375, 28178, 450775, 9780504, 1795265022} works for 64-bit integers.
answered Jul 11, 2012 at 10:05
-
$\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$– CharlesCommented 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$ Commented Nov 10, 2014 at 14:52