Elliptic Curve Primality Proof

This page : Definition(s) | Records | References | Related Pages |

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.

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

Record Primes of this Type

rank prime digits who when comment

1 10⁵⁰⁰⁰⁰ + 65859 50001 E3 Jun 2022 ECPP
2 R(49081) 49081 c70 Mar 2022 Repunit, unique, ECPP
3 10⁴⁰⁰⁰⁰ + 14253 40001 E3 Jun 2022 ECPP
4 p(1289844341) 40000 c84 Feb 2020 Partitions, ECPP
5 tau (47⁴¹⁷⁶) 38404 E3 Jun 2022 ECPP
6 2¹¹⁶²²⁴ - 15905 34987 c87 Nov 2017 ECPP
7 (14665 · 10³⁴¹¹⁰ - 56641)/9999 34111 c89 Mar 2018 ECPP, Palindrome
8 "10000000000000000000...(34053 other digits)...00000000000000532669" 34093 c84 Nov 2016 ECPP
9 (18²⁵⁶⁶⁷ - 1)/17 32218 E5 Jun 2022 Generalized repunit, ECPP
10 (2¹⁰⁶³⁹¹ - 1)/286105171290931103 32010 c95 Apr 2022 Mersenne cofactor, ECPP
11 V(148091) 30950 c81 Sep 2015 Lucas number, ECPP
12 U(148091) 30949 x49 Sep 2021 Fibonacci number, ECPP
13 Phi(36547, - 10) 29832 E1 Jun 2022 Unique, ECPP
14 2⁹⁹⁰⁶⁹ + 9814666761 29823 E4 Jun 2022 ECPP
15 " - τ(331²¹²⁸)" 29492 c80 Sep 2015 ECPP
16 V(140057) 29271 c76 Dec 2014 Lucas number, ECPP
17 (2⁹⁵³⁶⁹ + 1)/3 28709 x49 Aug 2021 Generalized Lucas number, Wagstaff, ECPP
18 - 30 · Bern(10264)/(1040513 · 252354668864651) 28506 c94 May 2021 Irregular, ECPP
19 (10²⁷⁶⁶⁹ + 7)/8313493832818655929448065598763458531111 27630 c96 Feb 2021 ECPP
20 U(130021) 27173 x48 May 2021 Fibonacci number, ECPP

ECPP From the Prime Glossary
Short introduction to ECPP

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
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, (http://dx.doi.org/10.1007/978-3-540-24847-7_14) MR 2137354
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, 1990. Amsterdam and New York, 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, MR 2000i:11190