Pollard's Rho Algorithm

Purpose: Find a non-trivial factor of a composite $n$ in expected $O(n^{1/4})$ time — enough to fully factor any 64-bit integer in microseconds.

Algorithm

1. If $n$ is even, return 2. If $n$ is prime (Miller-Rabin), it has no non-trivial factor.
2. Pick a pseudo-random map $f(x)=x^2+c(\mathrm{mod}n)$ with random $c\ne 0,-2$.
3. Iterate two pointers, $x$ (slow) and $y$ (fast, two steps per round) — a Floyd cycle detection walk.
4. At each step compute $g=\gcd (|x-y|,n)$.
   • $1<g<n$ → factor found.
   • $g=n$ → the walk collapsed; restart with a new $c$.
5. Recurse on $g$ and $n/g$.

Code

Brent’s variant, which batches the gcds and is roughly 25% faster:

using u64 = unsigned long long;
using u128 = __uint128_t;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
u64 pollard(u64 n) {
    if (n % 2 == 0) return 2;
    while (true) {
        u64 c = rng() % (n - 1) + 1;
        auto f = [&](u64 v) { return (u64)(((u128)v * v + c) % n); };
        u64 x = rng() % n, y = x, d = 1;
        while (d == 1) {
            x = f(x);
            y = f(f(y));
            if (x == y) { d = n; break; }        // walk collapsed
            d = __gcd(x > y ? x - y : y - x, n);
        }
        if (d != n) return d;                    // otherwise retry with a fresh c
    }
}
 
void factor(u64 n, vector<u64>& out) {
    if (n == 1) return;
    if (isPrime(n)) { out.push_back(n); return; }
    u64 d = pollard(n);
    factor(d, out);
    factor(n / d, out);
}

Batching the gcd

__gcd dominates the cost. Multiply up to 128 differences together modulo $n$ and take a single gcd; if it comes back as $n$, replay that block one step at a time. This is the standard “Brent-Pollard” speedup.

Paradigm

Randomized (Las Vegas). The answer is always correct; only the running time is random.

Complexity

• Time: expected $O(n^{1/4})$ = $O(\sqrt{p})$ where $p$ is the smallest prime factor
• Space: $O(1)$

Why It Works

The sequence $x_0,f(x_0),f(f(x_0)),\dots$ taken modulo $p$ (an unknown prime factor of $n$) behaves like a random walk on $p$ values. By the birthday paradox, it repeats after about $\sqrt{p}$ steps, forming the "$\rho$" shape that names the algorithm. When $x_i\equiv x_j(\mathrm{mod}p)$ but $x_i\not\equiv x_j(\mathrm{mod}n)$, the quantity $\gcd (|x_i-x_j|,n)$ is a proper divisor of $n$ containing $p$. We never know $p$, but the gcd finds it for us. Since the smallest prime factor of $n$ is at most $\sqrt{n}$, the expected cost is $O(n^{1/4})$.

Variants / Use Cases

• Brent’s improvement — replaces Floyd’s cycle detection with Brent’s, plus gcd batching
• Pollard’s Kangaroo — the same random-walk idea applied to discrete logarithms
• Lenstra ECM — better when $n$ has a medium-sized factor (up to ~60 digits)
• Quadratic Sieve / GNFS — for genuinely large semiprimes, where $\rho$ is hopeless
• Counting divisors of huge numbers, totient of a 64-bit number, primitive root search — all need factorisation first