Some integer factorization algorithms using elliptic curves

97. R. P. Brent, Some integer factorization algorithms using elliptic curves, Report CMA-R32-85, Centre for Mathematical Analysis, ANU, September 1985, ii+19 pp.

Abstract: dvi (2K), pdf (76K), ps (26K).

Technical Report: pdf (941K).


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 Technical Report was a preliminary (longer) version of Brent [102], and was one of the first publications on Hendrik Lenstra's elliptic curve method.


In the original version:

Equations (7.3) and (7.7) have obvious (easily corrected) errors.
In equation (1.1), the "(1+o(1))" factor should be inside the exponential.

Corrections have been made to the online version.

Go to next publication

Return to Richard Brent's index page