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?
$\begingroup$
$\endgroup$
2
1 Answer
$\begingroup$
$\endgroup$
2
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[318665857834031151167461]
(* 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.
-
$\begingroup$ Let me ask a subsidiary question. If I tested a sequence of integers up to $2\cdot 10^{5717}$ for which
PrimeQreported (* False *) can I state that the next prime member of this sequence (if it exists) is greater than $2\cdot 10^{5717}$? $\endgroup$ May 7, 2016 at 7:36 -
10$\begingroup$ Yes, the non-determinism in these tests only applies to primality: while a
Trueresult may happen to be wrong (with extremely small probability and no known examples), aFalseresult 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.) $\endgroup$– ilianMay 7, 2016 at 18:28
PrimeQhas 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. $\endgroup$