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).
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 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