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