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).
Abstract
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.
Comments
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.
Errata
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