Elliptic Curve Primality Proof
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.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).
rank prime digits who when comment 1 R(86453) 86453 E3 May 2023 Repunit, ECPP, unique 2 5104824 + 1048245 73269 E4 Feb 2023 ECPP 3 (2221509 - 1)/292391881 66673 E12 Oct 2023 Mersenne cofactor, ECPP 4 3125330 + 1968634623437000 59798 E4 Dec 2022 ECPP 5 "Ramanujan tau function at 199^4518" 57125 E3 Sep 2022 ECPP 6 (2174533 - 1)/193594572654550537 / 91917886778031629891960890057 52494 E5 Nov 2022 Mersenne cofactor, ECPP 7 1050000 + 65859 50001 E3 Jun 2022 ECPP 8 R(49081) 49081 c70 Mar 2022 Repunit, unique, ECPP 9 V(202667) 42355 E4 Nov 2023 Lucas number, ECPP 10 U(201107) 42029 E11 Sep 2023 Fibonacci number, ECPP 11 (2138937 + 1)/3 41824 E12 Oct 2023 Wagstaff, ECPP, generalized Lucas number 12 E(11848)/7910215 40792 E8 Aug 2022 Euler irregular, ECPP 13 1040000 + 14253 40001 E3 Jun 2022 ECPP 14 p(1289844341) 40000 c84 Feb 2020 Partitions, ECPP 15 (2130439 - 1)/260879 39261 E9 Feb 2023 Mersenne cofactor, ECPP 16 "tau(474176)" 38404 E3 Jun 2022 ECPP 17 V(183089) 38264 E4 Dec 2023 Lucas number, ECPP 18 (2127031 + 1)/3 38240 E5 Jan 2023 Wagstaff, ECPP, generalized Lucas number 19 378296 + 479975120078336 37357 E4 Jul 2022 ECPP 20 6320018 + 2001863 36020 E4 Jan 2023 ECPP
- 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, (http://dx.doi.org/10.1007/978-3-540-24847-7_14) 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, Amsterdam and New York, 1990. 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