An improved Monte Carlo factorization algorithm
51. R. P. Brent,
An improved Monte Carlo factorization algorithm,
BIT 20 (1980), 176-184.
Pollard's Monte Carlo factorization algorithm usually finds a factor
of a composite integer N in O(N1/4)
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.
The result improved the efficiency of
method [J. M. Pollard, BIT 15 (1975), 331-334.]
A modification of the method was used by Brent and Pollard
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
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