## Elliptic Curve Primality Proof |

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).

rank prime digits who when comment 1 "τ(157^{2206})"26643 FE1 Apr 2011 ECPP 2 6753^{5122}+ 5122^{6753}25050 FE1 Oct 2010 ECPP 3 " - τ(691^{1522})"23770 c65 Mar 2014 ECPP 4 2^{73845}+ 1471722230 c61 Dec 2013 ECPP 5 ((((((2521008887^{3}+ 80)^{3}+ 12)^{3}+ 450)^{3}+ 894)^{3}+ 3636)^{3}+ 70756)^{3}+ 9722020562 FE1 Jun 2006 ECPP, Mills' prime 6 (2^{63703}- 1)/4280841719169 c59 Jan 2014 Mersenne cofactor, ECPP 7 V(89849)18778 c70 Jan 2014 Lucas number, ECPP 8 primV(145353)18689 c69 Dec 2013 ECPP, Lucas primitive part 9 Phi(14943, - 100)18688 c47 Mar 2014 Unique, ECPP 10 Phi(741, - 63847^{9})/4425013290904011118666 c54 May 2013 ECPP 11 587 · 43103#/2310 + 65740218662 c35 Oct 2013 ECPP 12 587 · 43103#/2310 - 45570418662 c35 Jul 2013 ECPP 13 2^{61792}+ 2166118602 c61 Dec 2012 ECPP 14 V(81671)17069 c66 Sep 2013 Lucas number, ECPP 15 2^{56366}+ 3907916968 c61 Oct 2012 ECPP 16 39161#/2310 - 51047816901 c35 Apr 2013 ECPP 17 6521953289619 · 2^{55555}- 516737 c58 Apr 2013 Triplet (1), ECPP 18 "τ(571^{1090})"16526 c65 Jan 2014 ECPP 19 " - τ(79^{1570})"16386 c65 Feb 2014 ECPP 20 "τ(673^{1018})"15834 c65 Jul 2013 ECPP

- ECPP From the Prime Glossary
- Short introduction to ECPP
- Prime Links++'s programs to prove primality (including ECPP)

- AM93
A. O. L. AtkinandF. 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. MorainandT. 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. GoldwasserandJ. Kilian, "Primality testing using elliptic curves,"J. ACM,46:4 (1999) 450--472.MR 2002e:11182- GK86
S. GoldwasserandJ. 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.andLenstra, 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 K. Caldwell
© 1996-2014 (all rights reserved)