Pollard's Rho Algorithm - Algorithm

Algorithm

Inputs: n, the integer to be factored; and f(x), a pseudo-random function modulo n

Output: a non-trivial factor of n, or failure.

1. x ← 2, y ← 2; d ← 1
2. While d = 1:
   1. x ← f(x)
   2. y ← f(f(y))
   3. d ← GCD(|x − y|, n)
3. If d = n, return failure.
4. Else, return d.

Note that this algorithm may not find the factors and will return failure for composite n. In that case, use a different f(x) and try again. Note, as well, that this algorithm does not work when n is a prime number, since, in this case, d will be always 1. The algorithm is so-called because the values of f enter a period (mod d), resulting in a ρ shape when diagrammed.