## Elliptic Curve Factorization Method

A factorization method, abbreviated ECM, which 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 Method and Pollard p-1 Factorization Method.

See also Atkin-Goldwasser-Kilian-Morain Certificate, Elliptic Curve Primality Proving, Elliptic Pseudoprime

References

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, 26-37, 1990. ftp://nimbus.anu.edu.au/pub/Brent/rpb115.dvi.gz.

Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of , , 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.'' ftp://nimbus.anu.edu.au/pub/Brent/rpb156tr.ps.gz.

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

© 1996-9 Eric W. Weisstein
1999-05-25