Introduction to ECM

What does ECM mean? ECM stands for Elliptic Curve Method. It is currently the best algorithm known, among those whose complexity depends mainly on the size of the factor found (and not on the total size of the number to be factored, as in QS or NFS).

History. Richard Brent has predicted in 1985 in a paper entitled Some Integer Factorization Algorithms using Elliptic Curves that factors up to 50 digits could by found by ECM. Indeed, Peter Montgomery found in November 1995 a factor of 47 digits of 5^256+1, and Richard Brent set in October 1997 a new genuine record with a factor of 48 digits of 24^121+1.

Goal. The goal of ECMNET is to find large factors by ecm, mainly by contributing to the Cunningham project.

How to compute the group order of a successful elliptic curve? Use the following program written by Allan Steel in the Magma langage.

Bibliography. To know how ECM works and the history of the factorization of Fermat numbers by ECM and other methods, look at the paper Factorization of the tenth Fermat number by Richard Brent. Looking at the old paper Some Integer Factorization Algorithms using Elliptic Curves you'll see that very few improvements were made to ECM since 1985. One of these improvements is the FFT continutation invented by Peter Montgomery, and detailed in his dissertation entitled An FFT extension of ECM. You might also look at the paper A Practical Analysis of the Elliptic Curve Factoring Algorithm, by Bob Silverman and Sam Wagstaff, Mathematics of Computation vol. 61, July 1993. People reading german may look at Franz-Dieter Berger's Diplomarbeit entitled ``ECM Faktorisieren mit elliptischen Kurven''. Finally, have a look at the FactorWorld page from Scott Contini.