Integer Factorization Using Elliptic Curves

In 1987, Hendrik Lenstra published the landmark paper [#!lenstra:factorell!#] that introduces and analyzes the Elliptic Curve Method (ECM), which is a powerful algorithm for factoring integers using elliptic curves. Lenstra's method is also described in [#!silvermantate!#, §IV.4], [#!davenport!#, §VIII.5], and [#!cohen:ant!#, §10.3].

Lenstra's algorithm is well suited for finding ``medium sized'' factors of an integer $N$ , which today means between $10$ to $40$ decimal digits. The ECM method is not directly used for factoring RSA challenge numbers (see Section 1.1.3), but it is used on auxiliary numbers as a crucial step in the ``number field sieve'', which is the best known algorithm for hunting for such factorizations. Also, implementation of ECM typically requires little memory.

Lenstra