Pollard's rho algorithm

Pollard's rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective for a composite number having a small prime factor.

The ρ algorithm is based on Floyd's cycle-finding algorithm and on the observation that (as in the birthday problem) t random numbers x₁, x₂, ... , x_t in the range [1, n] will contain a repetition with probability P > 0.5 if t > 1.177n^1/2. The constant 1.177 comes from the more general result that if P is the probability that t random numbers in the range [1, n] contain a repetition, then P > 1 - exp{ - t²/2n }. Thus P > 0.5 provided 1/2 > exp{ - t²/2n }, or t² > 2n ln 2, or t > (2ln 2)^1/2n^1/2 = 1.177n^1/2.

The ρ algorithm uses g(x), a polynomial modulo n, as a generator of a pseudo-random sequence. (The most commonly used function is g(x) = (x² + 1) mod n.) Let's assume n = pq. The algorithm generates the sequence x₁ = g(2), x₂ = g(g(2)), x₃ = g(g(g(2))), and so on. Two different sequences will in effect be running at the same time—the sequence {x_k} and the sequence {x_k mod p}. Since p < n^1/2, the latter sequence is likely to repeat earlier than the former sequence. The repetition of the mod p sequence will be detected by the fact that gcd(x_k mod p - x_m mod p, n) = p, where k < m. Once a repetition occurs, the sequence will cycle, because each term depends only on the previous one. The name ρ algorithm derives from the similarity in appearance between the Greek letter ρ and the directed graph formed by the values in the sequence and their successors. Once it is cycling, Floyd's cycle-finding algorithm will eventually detect a repetition. The algorithm succeeds whenever the sequence {x_k mod p} repeats before the sequence {x_k}. The randomizing function g(x) must be a polynomial modulo n, so that it will work both modulo p and modulo n. That is, so that g(x mod p) ≡ g(x) (mod p).

The algorithm takes as its inputs $n$ , the integer to be factored; and $g(x)$ $g(x)$ , a polynomial $p(x)$ $p(x)$ computed modulo $n$ . This will ensure that if $p|n$ $p|n$ , and $x\equiv y{\bmod {p}}$ $x\equiv y{\bmod {p}}$ , then $g(x)\equiv g(y){\bmod {p}}$ $g(x)\equiv g(y){\bmod {p}}$ . In the original algorithm, $g(x)=(x^{2}-1){\bmod {n}}$ $g(x)=(x^{2}-1){\bmod {n}}$ , but nowadays it is more common to use $g(x)=(x^{2}+1){\bmod {n}}$ $g(x)=(x^{2}+1){\bmod {n}}$ . The output is either a non-trivial factor of $n$ , or failure. It performs the following steps:

...
Wikipedia