0

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.

pts
  • 607
  • Some references at A006945 at OEIS. And this at Wiki – Peter Phipps May 02 '20 at 13:41
  • I doubt that the range $2^{81}$ has been completely checked. I know that computers get more and more powerful, but this range makes me sceptical. But if there are counterexamples, they will be extremely rare, and it is well possible that there are none. – Peter May 02 '20 at 14:26
  • @PeterPhipps: I know about these links, both of them give an answer for about $n\le 2^{81}$, neither of them have any proven results for $2^{81}<n$. Do you have a link for larger values of $n$? – pts May 02 '20 at 15:45
  • 2
    @Peter It was definitely not done by checking all values, but by using an algorithm that finds all pseudoprimes to the first k prime bases. See the Sorenson/Webster reference for more info. For the OP's question, to the best of my knowledge, that 2015 result is the best we have so far, so no, no such deterministic set of bases is known. You can add more bases but we don't know where the first counterexample is -- it could be the first value after you stopped testing. Probably not, but the point is we don't know for sure. – DanaJ Jun 02 '20 at 08:12

0 Answers0