Pollard’s rho algorithm for factorization

Pollard's Rho Algorithm is a very interesting and quite accessible algorithm for factoring numbers. It was invented by John Pollard in 1975. It is not the fastest algorithm by far but in practice it outperforms trial division by many orders of magnitude. It is based on very simple ideas that can be used in other contexts as well. The amount of space required by this algorithm is very small or less and the running time taken by this particular algorithm is proportional to the square root of the s...