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$
5
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 -
$\begingroup$ No, it fails already on number 9 and on number 2047. The number you mentioned is much further. oeis.org/A006945 $\endgroup$ Apr 14 at 6:05
-
$\begingroup$ @ВалерийЗаподовников 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". $\endgroup$– ilianApr 14 at 19:10
-
$\begingroup$ @ilian ok. BTW, the test uses 2020's update Baillie-PSW now, see: mathematica.stackexchange.com/a/283692/82985 $\endgroup$ Apr 15 at 4:43
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$