## 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