There is a small prize offered for a number that is a pseudoprime base 2 and also a Lucas PSP. Probably the first examples will have many prime factors. The Carmichael numbers will usually be PSP base 2 and 3. There are an infinite number of them. I don't know the situation if we strengthen the requirement to MR-PSP. Richard Pinch has produced a list of PSP2s < 10^16; this would be a good starting point for trying out tests. We can decide if a number has >1 prime factor (i.e., it's composite). But we have no good way to show >2 prime factors. We can do it for some numbers by finding a factor F and showing either F or N/F is composite. Rich -----Original Message----- From: Michael Kleber [mailto:kleber@brandeis.edu] Sent: Tuesday, July 15, 2003 8:31 AM To: math-fun Subject: Re: [math-fun] Prime Testing technology 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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun