# Accuracy of PrimeQ function

Using PrimeQ in Mathematica 10 on integers up to $2\cdot 10^{5717}$ the function appears to work. The Documentation for Mathematica 5 says that PrimeQ is only good for integers up to $10^{16}$. Is there a definitive statement about the limit for PrimeQ implemented in Mathematica 10?

• As far as I know, the test used by PrimeQ has been proved correct for integers up to $2^{64}$. Also, no pseudoprime (a composite number passing the test) of any size has ever been found. Apr 27, 2016 at 18:55
• May 5, 2016 at 15:14

Turning my comment into an answer,

One of the tests performed by PrimeQ for machine-sized integers, namely Miller-Rabin using up to the first 12 primes as bases (as of version 10) has been proved correct for integers up to $2^{64}$ (in fact, the smallest number which that test falsely declares a prime is known to be $3186 65857 83403 11511 67461.$)

Of course,

PrimeQ

(* False *)


since it is rejected by a Lucas test (which is performed after a Miller-Rabin test with bases 2 and 3).

No pseudoprime (a composite number passing both tests) of any size has ever been found.

• Let me ask a subsidiary question. If I tested a sequence of integers up to $2\cdot 10^{5717}$ for which PrimeQ reported (* False *) can I state that the next prime member of this sequence (if it exists) is greater than $2\cdot 10^{5717}$? May 7, 2016 at 7:36
• Yes, the non-determinism in these tests only applies to primality: while a True result may happen to be wrong (with extremely small probability and no known examples), a False result is a guarantee of compositeness (assuming, of course, there are no bugs in the implementation, cosmic radiation doesn't flip random bits in the computer's memory etc.) May 7, 2016 at 18:28
• No, it fails already on number 9 and on number 2047. The number you mentioned is much further. oeis.org/A006945 Apr 14 at 6:05
• @ВалерийЗаподовников The number I mentioned, as explicitly stated in the answer (and in the linked paper) is the smallest strong pseudoprime to the first 12 prime bases. So when you say "it fails already on number 9 and on number 2047", I think there is some confusion as to what exactly is "it". Apr 14 at 19:10
• @ilian ok. BTW, the test uses 2020's update Baillie-PSW now, see: mathematica.stackexchange.com/a/283692/82985 Apr 15 at 4:43