Pollard's Rho Factorization

Factorize 64-bit integers into primes using Pollard's Rho with Miller-Rabin primality testing.

[Number Theory]|

Jul 9, 2026

|explanatory_notes.md|

#factorization#pollard-rho#number-theory#miller-rabin

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll mulmod(ll a, ll b, ll m) { return (__int128)a * b % m; }

ll powmod(ll a, ll d, ll m) {
    ll res = 1; a %= m;
    while (d > 0) {
        if (d & 1) res = mulmod(res, a, m);
        a = mulmod(a, a, m);
        d >>= 1;
    }
    return res;
}

bool millerRabin(ll n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0) return false;
    ll d = n - 1; int s = 0;
    while (d % 2 == 0) { d /= 2; s++; }
    for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (a >= n) continue;
        ll x = powmod(a, d, n);
        if (x == 1 || x == n - 1) continue;
        bool comp = true;
        for (int r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if (x == n - 1) { comp = false; break; }
        }
        if (comp) return false;
    }
    return true;
}

ll pollardRho(ll n) {
    if (n % 2 == 0) return 2;
    ll x = rng() % (n - 2) + 2, y = x;
    ll c = rng() % (n - 1) + 1, d = 1;
    while (d == 1) {
        x = (mulmod(x, x, n) + c) % n;
        y = (mulmod(y, y, n) + c) % n;
        y = (mulmod(y, y, n) + c) % n;
        d = __gcd(abs(x - y), n);
    }
    return d == n ? pollardRho(n) : d;
}

vector<ll> factorize(ll n) {
    if (n <= 1) return {};
    if (millerRabin(n)) return {n};
    ll d = pollardRho(n);
    auto a = factorize(d), b = factorize(n / d);
    a.insert(a.end(), b.begin(), b.end());
    sort(a.begin(), a.end());
    return a;
}

60 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Pollard's Rho

Factorize large integers (up to $2^{64}$ ) that are too big for trial division.

How It Works

Uses the pseudo-random function

f(x) = x^2 + c \pmod{n}

By the birthday paradox, after

O(\sqrt{p})

steps (where

p

is the smallest prime factor), two values

x_i, x_j

will satisfy

\gcd(|x_i - x_j|, n) > 1

Floyd's cycle detection (tortoise and hare) finds the collision without storing all values

\gcd = n

(trivial factor), retry with a different random

c

Miller-Rabin checks primality before attempting factorization

When to Use

Factoring numbers up to

2^{64}

that resist trial division

Problems requiring full prime factorization of large numbers

Combined with Miller-Rabin for fast factor-or-prove-prime decisions

Complexity

Pollard's Rho —

O(n^{1/4})

expected time per factor

Miller-Rabin —

O(k \log^2 n)

with

k = 12

witnesses for deterministic 64-bit results

Space —

O(1)

per call,

O(\log n)

for recursion

Notes

This template includes Miller-Rabin internally — no need to import the standalone Miller-Rabin template alongside it

The 12-witness set

\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37\}

is deterministic for all

n < 2^{64}