Possible Duplicate:
Do we really know the reliability of PrimeQ[n] (for $n>10^{16}$)?
The algorithm Mathematica uses for its PrimeQ[n] function is described at http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html 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 the book at
http://www.amazon.com/Course-Computational-Number-Theory-Curriculum/dp/0470412151/ref=sr_1_2?ie=UTF8&qid=1331771018&sr=8-2
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.