39
$\begingroup$

The algorithm Mathematica uses for its PrimeQ function is described on MathWorld. That web page says PrimeQ uses, "the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test." It also says,

"As of 1997, this procedure is known to be correct only for all $n<10^{16}$, but no counterexamples are known and if any exist, they are expected to occur with extremely small probability (i.e., much less than the probability of a hardware error on a computer performing the test)."

More details on the algorithm are given in A Course in Computational Number Theory by David Bressoud. That book says there are 52,593 integers less than $10^{16}$ that are 2- and 3- strong pseudoprimes. It also suggests Lucas pseudoprimes less than $10^{16}$ are rare. Number theory is a very rigorous field. Has any rigorous work been done to substantiate the claim above that, if a PrimeQ counterexamples exist, they are expected to occur with extremely small probability. All I can find so far is an extrapolation of the trend for ($n<10^{16}$), and that is a very hand-wavy argument.

Besides that, I am aware of no efforts to extend the brute force testing beyond $10^{16}$. With Moore's law and 15 years of work, considerable progress could have been made in that way.

  • 0
    @Ted: since this question was bounced here from mathematica.SE, I merged it with the copy you asked here earlier.2012-09-14

3 Answers 3

15

I and a number of others have proved that there are no BPSW-pseudoprimes below $2^{64}$. This builds on the work of Jan Feitsma around 2009. In particular this means that, barring programming errors, PrimeQ is correct for all values below $1.844\cdot10^{19}.$

  • 1
    @Szabolcs: I see that the result is being cited in the literature despite its lack of publication: http://ceur-ws.org/Vol-1326/020-Forisek.pdf gives it as "Feistma, J.: List of pseudoprimes and their prime factorizations, with additional annotations. http://www.cecm.sfu.ca/Pseudoprimes/index-2-to-64.html (2013)".2016-07-28
3

I think there is some confusion here (or at least that's how it seems to me, which is why I am writing this). Number theory is a part of mathematics and (arguably) not of the physical world. This means that certain things can be proved exactly and then (if we disregard the human problem of mistakes in proofs) they are "reliable". However, it is pretty easy to come up with statements ( "conjectures") in number theory that defeat all attempts to prove them yet counterexamples are equally hard to find. Such statements can be provably true, false (counter examples exist) but also they can be "true but unprovable" - meaning that neither counterexamples nor proofs will ever be found (of course that fact itself cannot ever be known). Can one speak about probability, reliability etc in such cases?

Strictly speaking: not at all. Thus PrimeQ is "reliable" only as far as it has been tested and nothing at all can be strictly said about its reliability for n larger than the numbers for which it has been tested. The same applies probability: there is no "strict" sense in which one can say that PrimeQ "probably" works for all n (or even "almost all"). The only reasons why people of probability etc in this context are psychological.

However, this does not mean that "empirical testing" of PrimeQ is useless. It of course means that the function is perfectly reliable for all n for which it has been tested. It is more convenient to use such a function that to store a huge list of known primes to look up every time you need to know if some number is a prime. PrimeQ is nothing more than a convenient replacement for a long list of known primes and testing it further simply makes this list longer. Another advantage of PrimeQ over such a list (of known primes) is that there is always some possibility that one day someone will produce a mathematical proof that PrimeQ always returns the right answer and then it will become 100% reliable. Most experts would say that the "probability" of this happening is small - but this is also only "psychology".

I just saw Daniel's comment. I have not seen R. Baillie and S. Wagstaff's paper so it maybe indeed true that there is a sense in which one can define the "probability" of such a counterexample and show that it is "small". One could then perhaps consider PrimeQ as "reliable" in this this particular sense beyond the numbers for which it has been tested. That, of course, would be useful for certain kind of applications but not for others (in particular not for asserting that a single large number that PrimeQ says is prime really is so).

  • 1
    I can't find any evidence that Element[n,Primes] calls PrimeQ. I can't find anything in the documentation about this. It is also hard to test it on examples without finding a case where PrimeQ fails. For example, PrimeQ[10^100 + 267] returns True. Element[10^100 + 267,Primes] also returns True. However, once we load the PrimalityProving` package we find that ProvablePrimeQ[10^100 + 267] also returns True. So it is hard to draw a conclusion except that this last computation seems to take longer than the other two.2012-03-22
3

Regarding the original question: it is not necessarily the case that Lucas pseudoprimes less than 1E16 are rare. The point is that, if you make a list of psp's base 2 and a list of Lucas psp's, then the two lists are observed to have very little, if any, overlap.

As for probabilities: In the Miller-Rabin test, if n is composite, then 3/4 of the bases are witnesses for the compositeness of n.

For the strong Lucas test, the corresponding probability (measuring (P,Q) pairs), is 11/15; see F. Arnault, "The Rabin-Monier Theorem for Lucas Pseudoprimes". Mathematics of Computation 66 (218) (April, 1997), pp. 869–881.