[math-fun] Prime Testing technology
I think this is a size record for verifying a prime with a generic method (that doesn't use any special form information about the number). The number tested has 6959 digits (23116 bits). The test took 1.5 years. The first 25% of the elapsed time reduced the size of the number being checked by 8%. ECPP can be helped by parallelism. The most important reduction is to find D values such that P (or 4P) = X^2 + D Y^2, and then one of P+1+-2X (or +-X) can be factored as small-stuff * Q. Q is a somewhat smaller prime than P. Finding the D values can be parallelized, and factoring the P+1+xxx can also be parallelized. Rich ---------------------- From: Hans Rosenthal <hans.rosenthal@t-online.de> Subject: ECPP record: (32*10^6959-23)/99 proven prime with Primo To: NMBRTHRY@LISTSERV.NODAK.EDU I would like to inform you that I have certified the primality of (32*10^6959-23)/99, a smoothly undulating palindromic prime (SUPP) [1] having 6959 decimal digits, with the program Primo [2], Marcel Martin's implementation of the elliptic curve primality proving (ECPP) algorithm. The Primo certificate of primality is available at http://www.ellipsa.net/primo/ecpp6959.zip (4457 KB) The certification of this ordinary prime was started on 21 January 2002 with Primo 1.1.0 (tests 1 to 47) and completed on 7 July 2003 with Primo 2.0.0 (tests 48 to 953) on an AMD Athlon 1.4 GHz. There was one relevant interruption of the certification process from 29 March 2003, 6:47, until 3 April 2003, 22:45. So the total running time amounts to approximately 527 days. There is a kind of ECPP diary of the certification progress available, which was started on 9 June 2002 at 21310 (of 23116) bits (so it is not complete). This diary can be found at http://www.ellipsa.net/primo/ecpp6959_diary.txt (9 KB) I thank Marcel Martin for his help and advice, and most of all, for making the ECPP algorithm available to the world of PC users in the most comfortable form I can imagine: his marvellous Primo. Hans Rosenthal [1] http://www.worldofnumbers.com/undulat.htm# [2] http://www.ellipsa.net/primo/record.html
Timing[PrimeQ[(32*10^6959 - 23)/99]] {198.245 Second, True} The above is from a Mathematica run. That's better than a 1.5 year run. I fairly certain that any of the major math programs is faster than Marcel Martin's Primo program. For what it's worth, (32*10^n - 23)/99 is composite from 6960 to 7500. --Ed Pegg Jr, www.mathpuzzle.com --- Richard Schroeppel <rcs@CS.Arizona.EDU> wrote:
I think this is a size record for verifying a prime with a generic method (that doesn't use any special form information about the number).
The number tested has 6959 digits (23116 bits). The test took 1.5 years. The first 25% of the elapsed time reduced the size of the number being checked by 8%. ........................ I would like to inform you that I have certified the primality of (32*10^6959-23)/99, a smoothly undulating palindromic prime (SUPP) [1] having 6959 decimal digits, with the program Primo [2], Marcel Martin's implementation of the elliptic curve primality proving (ECPP) algorithm.
On Tuesday, July 15, 2003, at 09:13 AM, Ed Pegg Jr wrote:
Timing[PrimeQ[(32*10^6959 - 23)/99]] {198.245 Second, True}
The above is from a Mathematica run. That's better than a 1.5 year run.
Surely you knew this alread, Ed, but for the record: Mma (and Maple etc) use a probabilistic primality testing algorithm ("Rabin-Miller strong pseudoprime"), which can report that a composite number is prime with (very) small probability. The ECPP method took 1.5 years, but it produced a "primality certificate" whose validity can now be checked easily, so there is now a short, rigorous proof that this particular number is prime. --Michael Kleber kleber@brandeis.edu
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
participants (3)
-
Ed Pegg Jr -
Michael Kleber -
Richard Schroeppel