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$
  • 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 '16 at 18:55
  • 2
    $\begingroup$ See math.stackexchange.com/questions/123465/… $\endgroup$ – Vaclav Kotesovec May 5 '16 at 15:14
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$
  • $\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$ – Frank M Jackson May 7 '16 at 7:36
  • 9
    $\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 '16 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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