Following up my previous mail,
Timing[PrimeQ[(32*10^6959 - 23)/99]] {198.245 Second, True}
The above is from a Mathematica run.[...]
From the Mathematica implementation details at http://documents.wolfram.com/v5/TheMathematicaBook/MathematicaReferenceGuide... SomeNotesOnInternalImplementation/A.9.4.html --------- * PrimeQ first tests for divisibility using small primes, then uses the Miller-Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test. * As of 1997, this procedure is known to be correct only for n < 10^16, and it is conceivable that for larger n it could claim a composite number to be prime. * The package NumberTheory`PrimeQ` contains a much slower algorithm which has been proved correct for all . It can return an explicit certificate of primality. --------- I had been under the mistaken impression that Mma's Miller- Rabin at least used (pseudo)random bases for PrimeQ. Since the algorithm is deterministic, there is (almost certainly, ie unless there's a big theorem about prime numbers waiting to be discovered) a well-defined "smallest n which Mma incorrectly claims is prime." Does anyone here know enough to estimate its size? (Or what its prime factorization is likely to look like? i.e. must all pq fail M-R for base 2 or 3?) --Michael Kleber kleber@brandeis.edu