Elliptic Curve Factorization Method -- from Wolfram MathWorld

Number Theory > Prime Numbers > Prime Factorization >

Recreational Mathematics > Mathematical Records >

Elliptic Curve Factorization Method

The elliptic curve factorization method, abbreviated ECM and sometimes also called the Lenstra elliptic curve method, is a factorization algorithm computes a large multiple of a point on a random elliptic curve modulo the number to be factored . It tends to be faster than the Pollard rho factorization and Pollard p-1 factorization methods.

Zimmermann maintains a table of the largest factors found using the ECM. As of April 2005, the largest prime factor found using the ECM had 66 decimal digits. The factor of was found by B. Dodson on Apr. 6, 2005 (Zimmermann).

REFERENCES:

Alpern, D. "Factorization Using the Elliptic Curve Method." http://www.alpertron.com.ar/ECM.HTM.

Atkin, A. O. L. and Morain, F. "Finding Suitable Curves for the Elliptic Curve Method of Factorization." Math. Comput. 60, 399-405, 1993.

Brent, R. P. "Some Integer Factorization Algorithms Using Elliptic Curves." Austral. Comp. Sci. Comm. 8, 149-163, 1986.

Brent, R. P. "Parallel Algorithms for Integer Factorisation." In Number Theory and Cryptography (Ed. J. H. Loxton). New York: Cambridge University Press, pp. 26-37, 1990.

Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of b-n+/-1, b=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, rev. ed. Providence, RI: Amer. Math. Soc., p. lxxxiii, 1988.

Eldershaw, C. and Brent, R. P. "Factorization of Large Integers on Some Vector and Parallel Computers." Australian National University, Technical Report TR-CS-95-01. January 1995. http://cs.anu.edu.au/techreports/1995/TR-CS-95-01.html.

Lenstra, A. K. and Lenstra, H. W. Jr. "Algorithms in Number Theory." In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (Ed. J. van Leeuwen). Amsterdam: Netherlands, Elsevier, pp. 673-715, 1990.

Lenstra, H. W. Jr. "Factoring Integers with Elliptic Curves." Ann. Math. 126, 649-673, 1987.

Montgomery, P. L. "Speeding the Pollard and Elliptic Curve Methods of Factorization." Math. Comput. 48, 243-264, 1987.

Zimmermann, P. "The ECMNET Project." http://www.loria.fr/~zimmerma/records/ecmnet.html.

Zimmermann, P. "ECM Top 100 Table." http://www.loria.fr/~zimmerma/records/top100.html.

CITE THIS AS:

Weisstein, Eric W. "Elliptic Curve Factorization Method." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/EllipticCurveFactorizationMethod.html