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.

$\endgroup$
7
  • 5
    $\begingroup$ 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. $\endgroup$
    – Daniel Lichtblau
    Mar 15, 2012 at 17:08
  • 2
    $\begingroup$ To complement that with a link to the paper (since I Googled it up anyway): ams.org/journals/mcom/1980-35-152/S0025-5718-1980-0583518-6/… $\endgroup$
    – Szabolcs
    Mar 15, 2012 at 19:01
  • 3
    $\begingroup$ 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 lattic $\endgroup$
    – alancalvitti
    Mar 21, 2012 at 18:14
  • $\begingroup$ A worthy comment, but I don't think it answers the question at all… $\endgroup$
    – F'x
    Mar 21, 2012 at 18:52
  • 1
    $\begingroup$ I think @alancalvitti was merely suggesting modesty of expectations. $\endgroup$
    – murray
    Mar 21, 2012 at 19:25

3 Answers 3

Reset to default
15
$\begingroup$

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}.$

$\endgroup$
8
  • $\begingroup$ Can you please provide references? $\endgroup$
    – Szabolcs
    Apr 2, 2014 at 17:31
  • $\begingroup$ janfeitsma.nl/math/psp2/index and cecm.sfu.ca/Pseudoprimes $\endgroup$
    – Charles
    Apr 2, 2014 at 17:55
  • $\begingroup$ 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? $\endgroup$
    – Szabolcs
    Apr 2, 2014 at 18:15
  • 2
    $\begingroup$ @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. $\endgroup$
    – Charles
    Apr 2, 2014 at 18:51
  • 1
    $\begingroup$ @Szabolcs: I see that the result is being cited in the literature despite its lack of publication: ceur-ws.org/Vol-1326/020-Forisek.pdf gives it as "Feistma, J.: List of pseudoprimes and their prime factorizations, with additional annotations. cecm.sfu.ca/Pseudoprimes/index-2-to-64.html (2013)". $\endgroup$
    – Charles
    Jul 28, 2016 at 22:20
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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).

$\endgroup$
5
  • 5
    $\begingroup$ 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). $\endgroup$
    – celtschk
    Mar 22, 2012 at 8:35
  • $\begingroup$ 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") $\endgroup$
    – Andrzej Kozlowski
    Mar 22, 2012 at 9:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrzej Kozlowski
    Mar 22, 2012 at 11:34
  • $\begingroup$ BTW, does Element[n,Primes] always give True when PrimeQ[n] does (i.e. also for unconfirmed cases)? $\endgroup$
    – celtschk
    Mar 22, 2012 at 13:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Andrzej Kozlowski
    Mar 22, 2012 at 15:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .