Pollard Rho Integer Factorization

The Pollard Rho algorithm turns collisions modulo an unknown factor of a composite integer n into a bounded integer-factor search. It applies Floyd's cycle-finding algorithm to a pseudo-random sequence defined by f(x) = (x*x + c) mod n.

Interactive Demonstration

Open the Pollard Rho Integer Factorization interactive experiment. You can use the Integer n, Polynomial constant, Seed, and Step limit controls to observe the algorithm behavior.

1. Select Integer n as 8051, Polynomial constant as 1, and Seed as 2.
2. Set the Step limit to 16.
3. Observe that the Iterations performed is 3, and the Factor found is 97 with a Cofactor of 83.
4. The explanatory curve shows the Floyd walk along the nodes. Modifying the seed changes the path taken, but may still converge to the same factor.