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.

  • 5
    R. Baillie and S. Wagstaff. Lucas sseudoprimes. Mathematics of Computation 35(152):1391-1417. 1980. This remains an excellent reference for the probabilistic test, insofar as it attempts to show why there might be no exceptions, and that in some sense the likelihood of such is small.2012-03-15
  • 2
    To complement that with a link to the paper (since I Googled it up anyway): http://www.ams.org/journals/mcom/1980-35-152/S0025-5718-1980-0583518-6/S0025-5718-1980-0583518-6.pdf2012-03-15
  • 3
    I offer this evidence: 1. The Collatz (ie, 3x+1 problem) conjecture is still open after 70+ years of work. The smallest ~10^18 natural numbers have been computationally tested and found to be in the basin of attraction of the presumed only cycle {1,2,4}. 2. A proof of the Twin Primes conjecture has been published and retracted. These should remind that even basic arithmetic questions can be intractable. As in combinatorial geometry, graph theory and other fields, high dimensional spaces can have non-intiuitive properties. (in number theory an appropriate dimension is that of the divisor lattic2012-03-21
  • 0
    A worthy comment, but I don't think it answers the question at all…2012-03-21
  • 1
    I think @alancalvitti was merely suggesting modesty of expectations.2012-03-21
  • 0
    I'll be glad to help further and provide references - but it's a wide web of references. Can you specify which parts went over your head? I tried to use standard language. many concepts have multiple definitions, eg "random," "dimension."2012-03-21
  • 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}.$

  • 0
    Can you please provide references?2014-04-02
  • 0
    http://www.janfeitsma.nl/math/psp2/index and http://www.cecm.sfu.ca/Pseudoprimes/2014-04-02
  • 0
    My point was this: you said, "I and a number of others have proved ...", but there are no references for that, and people don't know who you are to search for it. Suppose someone needs to cite a proof that the prime checking method from the method is indeed reliable up to 2^64, but is not particularly interested in the details of the method itself, just wants to check if some numbers are primes. Are there published peer reviewed articles to cite on the topic?2014-04-02
  • 2
    @Szabolcs: I certainly didn't publish my work and I doubt the others did. Probably when Feitsma publishes his underlying work he'll do yet another verification of the BPSW part and then you'll have a reference. He only restarted work on the paper late last year IIRC, though, so it will be a while before it sees print.2014-04-02
  • 0
    Thanks for the information!2014-04-02
  • 0
    @Szabolcs: Are you looking for a citation for a paper you're working on? I could drop Jan a line if you're really curious.2014-04-02
  • 0
    Thank you Charles, at this stage it is not yet necessary (no paper yet). If it becomes necessary in the future I might ask you.2014-04-02
  • 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).

  • 5
    However a "honest" function could return three values: `False` for when the test fails, `True` for when the test succeeds and the number is in the tested range, and `Maybe` (or simply leaving the call unevaluated) for the case when the test succeeds, but the number is outside the tested range. There could be a variable `$PrimeQReliableMax` which stores the tested maximum and could be set to a higher value if one knows that in the mean time more numbers were tested (or to `Infinity` if it was proven to work, or if a `True` result even for unproven cases is desired).2012-03-22
  • 0
    Yes, I think that would be a good idea. It would also give some incentive for people to keep testing PrimeQ: Wolfram could then "improve" Mathematica while hardly changing anything ("in the new version PrimeQ returns "True" for larger n")2012-03-22
  • 1
    Of course that would violate the principle that all Mathematica's functions ending in Q return only True or False (but this could be dealt with via a message). As it is, I don't think PrimeQ should really be interpreted as "is this number a prime?" but as "does it pass the PrimeQ test?". In this sense, it is still an "honest" function.2012-03-22
  • 0
    BTW, does `Element[n,Primes]` always give `True` when `PrimeQ[n]` does (i.e. also for unconfirmed cases)?2012-03-22
  • 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.