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 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).  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
1V(148091) 30950 c81 Sep 2015 Lucas number, ECPP
2" - τ(3312128)" 29492 c80 Sep 2015 ECPP
3V(140057) 29271 c76 Dec 2014 Lucas number, ECPP
4"τ(1572206)" 26643 FE1 Apr 2011 ECPP
5(283339 + 1)/3 25088 c54 Sep 2014 ECPP, generalized Lucas number, Wagstaff
667535122 + 51226753 25050 FE1 Oct 2010 ECPP
7floor((3 / 2)137752) + 13566 24257 c35 Mar 2015 ECPP
8" - τ(6911522)" 23770 c65 Mar 2014 ECPP
9"τ(2571698)" 22506 c72 Apr 2014 ECPP
101022250 + 57913 22251 c35 May 2014 ECPP
11273845 + 14717 22230 c61 Dec 2013 ECPP
12273360 + 10711 22084 c61 Sep 2014 ECPP
13U(104911) 21925 c82 Oct 2015 Fibonacci number, ECPP
14((((((25210088873 + 80)3 + 12)3 + 450)3 + 894)3 + 3636)3 + 70756)3 + 97220 20562 FE1 Jun 2006 ECPP, Mills' prime
15Phi(23749, - 10) 20160 c47 Apr 2014 Unique, ECPP
16"τ(6191296)" 19900 c72 Aug 2014 ECPP
17V(94823) 19817 c73 May 2014 Lucas number, ECPP
18Phi(2685, 67588246166904)/(72171843001561 · 182332981 · 1923646771 · 174457892355841 · 21784054190313871) 19632 c54 Mar 2015 ECPP
19(263703 - 1)/42808417 19169 c59 Jan 2014 Mersenne cofactor, ECPP
20V(89849) 18778 c70 Jan 2014 Lucas number, ECPP

(up) Related Pages

(up) References

A. O. L. Atkin and F. Morain, "Elliptic curves and primality proving," Math. Comp., 61:203 (July 1993) 29--68.  MR 93m:11136
A. O. L. Atkin, "Lecture notes of a conference," Boulder Colorado, (August 1986) Manuscript. [See also [AM93].]
Franke, J., Kleinjung, T., Morain, F. and Wirth, T., Proving the primality of very large numbers with fastECPP.  In "Algorithmic number theory," Lecture Notes in Comput. Sci. Vol, 3076, Springer, Berlin, 2004.  pp. 194--207, ( MR 2137354
S. Goldwasser and J. Kilian, "Primality testing using elliptic curves," J. ACM, 46:4 (1999) 450--472.  MR 2002e:11182
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,
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, 1990.  Amsterdam and New York, pp. 673-715, MR 1 127 178
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, MR 2000i:11190
Chris K. Caldwell © 1996-2015 (all rights reserved)