An improved Monte Carlo factorization algorithm
51. R. P. Brent,
An improved Monte Carlo factorization algorithm,
BIT 20 (1980), 176-184.
MR 82a:10007.
Abstract:
dvi (2K),
pdf (64K),
ps (25K),
Paper:
pdf (534K).
Abstract
Pollard's Monte Carlo factorization algorithm usually finds a factor
of a composite integer N in O(N1/4)
arithmetic operations.
The algorithm is based on a cycle-finding algorithm of Floyd.
We describe a cycle-finding algorithm which is about 36 percent faster
than Floyd's (on the average), and apply it to give a Monte Carlo
factorization algorithm which is similar to Pollard's but about
24 percent faster.
Comments
The result improved the efficiency of
Pollard's "rho"
method [J. M. Pollard, BIT 15 (1975), 331-334.]
A modification of the method was used by Brent and Pollard
[61]
to factor the eighth Fermat number.
Although the Pollard rho method for integer factorization has largely
been supplanted by the elliptic curve method,
it is still useful for finding factors of size up to about twelve decimal
digits. Also, related ideas are used in the Pollard rho method for
discrete logarithms.
A slightly more efficient cycle finding algorithm is described in:
Gabriel Nivasch, Cycle detection using a stack,
Information Processing Letters, 2004.
Go to next publication
Return to Richard Brent's index page