13
$\begingroup$

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?

$\endgroup$
2
  • 8
    $\begingroup$ 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. $\endgroup$
    – ilian
    Apr 27, 2016 at 18:55
  • 2
    $\begingroup$ See math.stackexchange.com/questions/123465/… $\endgroup$ May 5, 2016 at 15:14

1 Answer 1

14
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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}$? $\endgroup$ May 7, 2016 at 7:36
  • 10
    $\begingroup$ 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.) $\endgroup$
    – ilian
    May 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$
    – ilian
    Apr 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.