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
- 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, May 1986. New York, NY, 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