An improved Monte Carlo factorization algorithm

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. Show more