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

Question

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.

Answer 1

According to A014233,

$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}$$

Answer 2

If, for some reason, you insist on only using the first n prime bases, then you need 12 bases for cover the 64-bit space. If you use some of the better sets people have found, then the best we know of is 7 (http://miller-rabin.appspot.com/) and depending on the input size you may be able to use fewer. If you're willing to use a 32k hash table, this can be brought down to 3. The BPSW test can be made to run in about the cost of 2.7x M-R tests and doesn't require the hash table.

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.