Some integer factorization algorithms using elliptic curves

102. R. P. Brent, Some integer factorization algorithms using elliptic curves, Australian Computer Science Communications 8 (1986), 149-163. Retyped and postscript added 1998. arXiv:1004.3366v1

Abstract: dvi (3K), pdf (30K).

Paper: dvi (29K), pdf (200K), ps (89K).


Lenstra's integer factorization algorithm is asymptotically one of the fastest known algorithms, and is ideally suited for parallel computation. We suggest a way in which the algorithm can be speeded up by the addition of a second phase. Under some plausible assumptions, the speedup is of order log(p), where p is the factor which is found. In practice the speedup is significant. We mention some refinements which give greater speedup, an alternative way of implementing a second phase, and the connection with Pollard's "p-1" factorization algorithm.


This was one of the first papers to consider ECM. A preliminary (longer) version appeared as Brent [97].

One of ECM's early successes was the complete factorization of the 617-decimal digit Fermat number F11; see Brent [113, 115, 161]. A later success was the (more difficult) factorization of F10.

Go to next publication

Return to Richard Brent's index page