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 $N$. 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 $b^n\pm 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.'' 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.