![]() |
Elliptic Curve Primality Proof |
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 p(1289844341) 40000 c84 Feb 2020 Partitions, ECPP 2 2116224 - 15905 34987 c87 Nov 2017 ECPP 3 (14665 · 1034110 - 56641)/9999 34111 c89 Mar 2018 ECPP, Palindrome 4 "10000000000000000000...(34053 other digits)...00000000000000532669" 34093 c84 Nov 2016 ECPP 5 V(148091) 30950 c81 Sep 2015 Lucas number, ECPP 6 " - τ(3312128)" 29492 c80 Sep 2015 ECPP 7 V(140057) 29271 c76 Dec 2014 Lucas number, ECPP 8 (1027669 + 7)/8313493832818655929448065598763458531111 27630 c96 Feb 2021 ECPP 9 546351925018076058 · Bern(9702)/129255048976106804786904258880518941 26709 c77 Jan 2021 Irregular, ECPP 10 "τ(1572206)" 26643 FE1 Apr 2011 ECPP 11 1025333 - 2 · 105182 - 3 25333 c95 Aug 2020 ECPP 12 Phi(12345, 7176)/31531760245313526865033921 25331 c54 Jun 2017 ECPP 13 (284211 - 1)/1347377 / 31358793176711980763958121 / 3314641676042347824169591561 25291 c95 Sep 2020 Mersenne cofactor, ECPP 14 (283339 + 1)/3 25088 c54 Sep 2014 ECPP, generalized Lucas number, Wagstaff 15 67535122 + 51226753 25050 FE1 Oct 2010 ECPP 16 (282939 - 1)/883323903012540278033571819073 24938 c84 Feb 2021 Mersenne cofactor, ECPP 17 floor((3 / 2)137752) + 13566 24257 c35 Mar 2015 ECPP 18 " - τ(6911522)" 23770 c65 Mar 2014 ECPP 19 798 · Bern(8766)/(2267959 · 6468702182951641) 23743 c94 Jan 2021 Irregular, ECPP 20 primV(67, - 1, 13081)/65419672274940815357 23451 c84 Oct 2019 ECPP
- 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