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.
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
"p-1" factorization algorithm.
This was one of the first papers to consider
A preliminary (longer) version appeared as Brent
One of ECM's early successes was the complete factorization of
the 617-decimal digit Fermat number
A later success was the (more difficult) factorization of
Go to next publication
Return to Richard Brent's index page