# Bases required for prime-testing with Miller-Rabin up to $2^{63}-1$

This webpage (as well as Wikipedia) explains how one can use the Miller-Rabin test to determine if a number in a particular range is prime. The size of the range determines the number of required bases to test. For example:

If $n < 9,080,191$ is a base $31$ and base $73$ strong probable prime, then $n$ is prime.

If $n < 2,152,302,898,747$ is a base $2, 3, 5, 7,$ and $11$ strong probable prime, then $n$ is prime.

How many bases must I test to deterministically tell if any integer $n < 2^{63}-1$ is prime?

As one may guess by the bound, I'm interested in using this approach for primality testing in programs. Assuming the truth of the extended Riemann hypothesis (which I'd be willing to do, given that I am using this code simply for competitions and/or "toy" problems, but not for high-risk applications), it is sufficient to test all bases $a$ in the range $1<a<2\log^2(n)$.

Reducing the number of bases I need to check could dramatically improve the runtime of my code; thus, I was wondering if there was a smaller number of bases.

• You might consider using the Baillie Pomerance Selfridge Wagstaff test, which has no false positives below $2^{64}$ and typically should be faster than twelve strong Fermat tests. (Almost all non-primes will be found by the base-$2$ test already.) – Daniel Fischer Nov 3 '14 at 21:29
• @DanielFischer Thanks! I'll look at that test, too. The fact that the wiki page says "there are also no known composite numbers above $2^{64}$ that pass the test" is quite intriguing. – apnorton Nov 3 '14 at 21:33
• @anorton: There are believed to be infinitely many BPSW-pseudoprimes, but none have been found. See pseudoprime.com/pseudo.html and especially the Alford-Grantham list. – Charles Nov 3 '14 at 23:50

$a(12) > 2^{64}$. Hence the primality of numbers $< 2^{64}$ can be determined by asserting strong pseudoprimality to all prime bases $\leqslant 37 (= \text{prime}(12))$. Testing to prime bases $\leqslant 31$ does not suffice, as $a(11) < 2^{64}$ and $a(11)$ is a strong pseudoprime to all prime bases $\leqslant 31 (= \text{prime}(11))$. [Joerg Arndt, Jul 04 2012]
$$a(11) = 3825123056546413051 < 2^{62}$$
My preference is to do a tiny bit of trial division (primes to 53, but some people like less), then 1 M-R if $n < 341531$, 2 M-R if $n < 1050535501$, otherwise BPSW. The AES Lucas variant using Montgomery math is fastest for me, but it's up to you -- standard, strong, extra strong, AES, and others have all been shown to work. Just make sure you test whatever you end up using.