An FFT extension of the elliptic curve method of factorization
Peter L. Montgomery · 1992
Factorization of arbitrary integers is believed to be a hard problem. The Elliptic Curve Method (ECM), discovered by Hendrik Lenstra, Jr. in 1985, is the best known method for finding 20- to 30-digit factors of a large integer N. The ECM algorithm has two main steps. It computes a large multiple of an element P of an elliptic curve group modulo N, obtaining another element Q. Step 1 succeeds if we strike the identity element of the group modulo p for some prime divisor p of N. If Step 1 is unsuccessful, then Step 2 compares multiples of Q, looking for a duplicate modulo some p/N. This thesis describes how to apply convolutions modulo N and last polynomial arithmetic algorithms in the search. This effectively increases the range of ECM by a factor of 100 with about twice the combined Step 1/Step 2 execution time previously required (but more memory). The revised algorithm was tested by trying it on the RSA Factoring Challenge list. We discuss many architectural considerations relating to the implementation, such as the identifying which portions of the computation can be vectorized or parallelized. We also discuss the algorithms for computer arithmetic. We give a detailed analysis of intermediate results of the fast polynomial GCD algorithm. We give a family of elliptic curves with torsion group of order 16 and positive rank over $\doubq$, and compare the smoothness of their orders to the smoothness of curves with torsion group of order 12.