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