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