Small Miller-Rabin bases for 82 ... 307 bits

75 Views Asked by At

Let's suppose we want to test the positive integer $n$ for primality using Miller-Rabin and a few pre-chosen bases ($a$). Previous results ([1], [2] and Theorem 1.1 in [3]) indicate that if $n$ is smaller than $2^{81}$, then the first 13 primes are good enough as $a$: if $n$ passes the test with all the first 13 primes as bases, then $n$ is a prime.

Is there a published, short list of bases which works for larger values of $n$, e.g. all $2^{81}\le n<2^{307}$? Preferably the list of bases should be short, but it doesn't have to be optimal. Also the actual base values should be small (e.g. the first few primes), for fast exponentiation.