Pollard Rho Integer Factorization

Independent Original Case

Consider factoring n = 91 with polynomial constant c = 1 and starting seed = 2. The sequence starts at x = 2. In each iteration, we update the tortoise as x = f(x) and the hare as y = f(f(y)), then calculate d = gcd(|x - y|, n).

1. Initial state (Step 0): x = 2, y = 2, gcd = 1. No iterations.
2. Iteration 1:
   Tortoise x = f(2) = (2*2 + 1) mod 91 = 5.
   Hare y = f(f(2)) = f(5) = (5*5 + 1) mod 91 = 26.
   Distance |x - y| = |5 - 26| = 21.
   d = gcd(21, 91) = 7.

Because d = 7 is greater than 1, we stop. We have successfully found a non-trivial factor 7 and its cofactor 13.

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.

Known Limitations

If the sequence enters a cycle where the GCD evaluated to n, the cycle finding has failed, which requires restarting the process with a different seed or polynomial constant c. The algorithm returning d = n does not prove primality; primality testing algorithms like Miller-Rabin must be used instead. Step limits are enforced because Pollard's Rho is a probabilistic algorithm, and there is no strict upper bound on iterations before cycle detection, though it typically takes O(n^(1/4)) time.

References

The properties of the cyclic pseudo-random sequence mapped against an unknown prime factor drive the algorithm.

• KTH DD2440: Advanced Algorithms (Lecture 6)