The Top Twenty--a Prime Page Collection

Elliptic Curve Primality Proof

This page : Definition(s) | Records | References | Related Pages | RSS 2.0 Feed
  View this page in:   language help

The Prime Pages

The Prime Pages keeps a list of the 5000 largest known primes, plus a few each of certain selected archivable forms and classes. These forms are defined in this collection's home page. This page is about one of those forms. Comments and suggestions requested.

(up) Definitions and Notes

This page lists record primes that were first proven prime by the elliptic curve primality proving algorithm.  It is shown here as a convenience for those watching the heated contest between the chief ECPP programmers.  Originally these were François Morain (who first set a titanic prime record for proving primality via ECPP) and Marcel Martin (who wrote a version called Primo for Windows machines).  Both programs available).  In 2003, J. Franke, T. Kleinjung and T. Wirth greatly increased the size of numbers that could be handled with a new program of their own.  Morain has worked with this trio and they have both improved their programs [FKMW2003].  Martin's Primo is by far the easiest of these programs to set up and use.  There seems to be some question which is fastest on a single CPU.

ECPP has replaced the groups of order n-1 and n+1 used in the classical test with a far larger range of group sizes (see our page on elliptic curve primality proving).  The idea is that we can keep switching elliptic curves until we find one we can "factor".  This improvement comes at the cost of having to do a great deal of work to find the actual size of these groups--but works for all numbers, not just those with very special forms.

About 1986 S. Goldwasser & J. Kilian [GK86] and A. O. L. Atkin [Atkin86] introduced elliptic curve primality proving methods.  Atkin's method, ECPP, was implemented by a number of mathematicians, including Atkin & Morain [AM93].  Heuristically, ECPP is O((log n)5+eps) (with fast multiplication techniques) for some eps > 0 [LL90].  It has been proven to be polynomial time for almost all choices of inputs.  A version attributed to J. O. Shallit is O((log n)4+eps). Franke, Kleinjung and Wirth combined with Morain to improve their respective programs (both now use Shallit's changes), creating what they "fastECPP" [FKMW2003]. 

The editors expect this page should remain our only Top Twenty Page dedicated to a proof method rather than a form of prime.  Note that "fastECPP" is simply a name--their use of the adjective 'fast' should not be construed as a comparison to programs by other authors (which may also follow Shallit's approach).

(up) Record Primes of this Type

rankprime digitswhowhencomment
1((((((25210088873+80)3+12)3+450)3+894)3+3636)3+70756)3+97220 20562 FE1 Jun 2006 ECPP, Mills' prime
226384405+44052638 15071 FE3 Jul 2004 ECPP
3(21474836471597-1)/1361551397315358942 14885 FE7 Mar 2009 ECPP
4(242737+1)/3 12865 M Aug 2007 ECPP, generalized Lucas number, Wagstaff
56 · Bern(4306)/2153 10342 FE8 Apr 2009 Irregular, ECPP
659056921173 · 234030+7 10255 FE6 Mar 2009 ECPP
712343265+32651234 10094 FE1 Aug 2005 ECPP
8Phi(427, -1028) 10081 FE9 May 2009 Unique, ECPP
927392930+29302739 10073 FE1 Jan 2005 ECPP
102072644824759 · 233333+5 10047 FE5 Nov 2008 Triplet (3), ECPP
116483571+3571648 10041 M Dec 2003 ECPP
12109999+33603 10000 FE2 Aug 2003 ECPP
1326582659+26592658 9106 FE1 Aug 2005 ECPP
14138148+27162197 9077 M Jan 2005 ECPP
1523192680+26802319 9020 M Apr 2004 ECPP
16229727+20273 8949 c18 Jul 2009 ECPP
17Phi(1887, -11758041)/(7549 · 19070968058734261) 8125 c13 Jul 2009 ECPP
1816472518+25181647 8100 FE1 Mar 2005 ECPP
191973514+3514197 8063 M Aug 2004 ECPP
2019952438+24381995 8046 FE1 Sep 2003 ECPP

(up) Related Pages

(up) References

AM93
A. O. L. Atkin and F. Morain, "Elliptic curves and primality proving," Math. Comp., 61:203 (July 1993) 29--68.  MR 93m:11136
Atkin86
A. O. L. Atkin, "Lecture notes of a conference," Boulder Colorado, (August 1986) Manuscript. [See also [AM93].]
FKMW2003
J. Franke, T. Kleinjung, F. Morain and T. Wirth, "Proving the primality of very large numbers with fastecpp," (2003) Available from ftp://lix,polytechnique.fr/pub/submissions/morain/Preprints/large.ps.gz.
GK1999
S. Goldwasser and J. Kilian, "Primality testing using elliptic curves," J. ACM, 46:4 (1999) 450--472.  MR 2002e:11182
GK86
S. Goldwasser and J. Kilian, Almost all primes can be quickly certified.  In "STOC'86, Proceedings of the 18th Annual ACM Symposium on the Theory of Computing (Berkeley, CA, 1986)," ACM, New York, NY, May 1986.  pp. 316--329,
LL90
Lenstra, Jr., A. K. and Lenstra, Jr., H. W., Algorithms in number theory.  In "Handbook of Theoretical Computer Science, Vol A: Algorithms and Complexity," The MIT Press, Amsterdam and New York, 1990.  pp. 673-715, MR 1 127 178
Morain98
F. Morain, Primality proving using elliptic curves: an update.  In "Algorithmic Number Theory, Third International Symposium, ANTS-III," J. P. Buhler editor, Lecture Notes in Comput. Sci. Vol, 1423, Springer-Verlag, June 1998.  pp. 111--127, Available from http://www.lix.polytechnique.fr/~morain/Articles/articles.english.html.  MR 2000i:11190
Chris Caldwell © 1996-2009 (all rights reserved)