Miller-Rabin and Pollard Rho
The standard 64-bit primality and factorization toolkit once trial division stops being realistic.
Miller-Rabin and Pollard Rho
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
For serious 64-bit primality and factorization tasks, trial division is not enough. The standard contest toolkit is:
Miller-Rabin to decide primality quickly,
Pollard Rho to split a composite number into nontrivial factors.
The two techniques are usually used together, not separately.
Problem-Driven Motivation
Suppose inputs are arbitrary 64-bit integers and the task asks for:
primality testing for many queries,
full prime factorization,
divisor counts or multiplicative-function values of huge numbers.
Trial division up to \(\sqrt{n}\) is too slow once \(n\) reaches around \(10^{18}\). But a full heavyweight number theory library is unnecessary. What we need is:
Fast primality rejection, plus a practical way to split composites.
Recognition Pattern
Reach for this pair when:
numbers fit in 64 bits but are too large for \(\sqrt{n}\) methods,
randomization is acceptable,
the task needs exact factorization, not just small-prime preprocessing.
If all numbers are small enough for a sieve or bounded trial division, this machinery is unnecessary.
Derivation
Miller-Rabin.
For odd prime \(n\), write \[ n-1 = d \cdot 2^s \] with \(d\) odd. Then for any base \(a\), the powers \[ a^d,\ a^{2d},\ a^{4d},\ \dots,\ a^{2^{s-1}d} \] must satisfy a very rigid modular pattern. Composites usually violate it, and such a violating base is called a witness.
So Miller-Rabin is not proving primality directly. It is trying to find a contradiction to primality extremely quickly.
Pollard Rho.
Once we know \(n\) is composite, we do not need the smallest factor. Any nontrivial factor is enough. Pollard Rho creates a pseudorandom walk \[ x_{k+1} = f(x_k) \bmod n \] and compares two iterates with Floyd's cycle trick. If the walk collides modulo one hidden prime factor earlier than it collides modulo the full number, the gcd of the difference with \(n\) leaks a nontrivial factor.
Worked Problem
Problem.
Given many 64-bit integers, return the largest prime factor of each.
Why naive fails.
Trial division up to \(\sqrt{n}\) is far too slow on worst-case semiprimes near \(10^{18}\).
Step 1: primality test.
Run deterministic Miller-Rabin for 64-bit integers using a fixed witness set. If \(n\) is prime, stop immediately.
Step 2: split composites.
If \(n\) is composite, run Pollard Rho until it returns a nontrivial divisor \(d\).
Step 3: recurse.
Factor \(d\) and \(n/d\) recursively. The recursion eventually bottoms out at primes because every split strictly reduces the number.
Why this is practical.
Miller-Rabin prevents wasting Pollard-Rho effort on actual primes. Pollard Rho only needs one factor, not the best factor, so random splitting is enough.
Implementation Reasoning
Three implementation details matter a lot:
use
__int128for modular multiplication to avoid overflow,hard-code the deterministic witness set valid for 64-bit integers,
restart Pollard Rho with a new random constant if one walk fails by returning \(n\).
The recursive factorizer is short because Miller-Rabin and Pollard Rho each do one job cleanly.
Correctness Intuition
Miller-Rabin is correct because primes satisfy the strong modular squaring pattern, so any witness really proves compositeness. Pollard Rho is effective because the pseudorandom walk tends to collide modulo hidden prime factors before it fully cycles modulo \(n\), and that mismatch is exposed by the gcd.
Complexity Analysis
Miller-Rabin on 64-bit integers uses a constant number of witnesses, so its cost is essentially a small number of modular exponentiations. Pollard Rho is randomized, so the cleanest bound is probabilistic, but in practice it is fast enough for standard contest-sized 64-bit inputs.
Common Pitfalls
Overflowing modular multiplication without
__int128.Using an insufficient witness set and silently misclassifying a composite as prime.
Forgetting small cases like \(n < 2\), even numbers, or small primes.
Treating Pollard Rho as deterministic; failed random walks need restarts.
Variants and Failure Modes
For very small numbers, trial division is simpler.
For larger-than-64-bit integers, the same ideas still work but the implementation is no longer deterministic with the same witness set.
Small-prime stripping before Pollard Rho is often a good practical improvement.
Practice Problems
Factor arbitrary 64-bit integers.
Answer many primality queries on large inputs.
Compute divisor counts or largest prime factors from the returned factorization.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
using u64 = uint64_t;
u64 gcd_u64(u64 a, u64 b) {
while (b != 0) {
u64 t = a % b;
a = b;
b = t;
}
return a;
}
u64 mod_mul(u64 a, u64 b, u64 mod) {
u64 result = 0;
while (b > 0) {
if (b & 1) {
if (result >= mod - a) result -= mod - a;
else result += a;
}
b >>= 1;
if (b == 0) break;
if (a >= mod - a) a -= mod - a;
else a += a;
}
return result;
}
u64 mod_pow(u64 a, u64 e, u64 mod) {
u64 result = 1;
while (e > 0) {
if (e & 1) result = mod_mul(result, a, mod);
a = mod_mul(a, a, mod);
e >>= 1;
}
return result;
}
bool is_prime(u64 n) {
if (n < 2) return false;
for (u64 p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
if (n % p == 0) return n == p;
}
u64 d = n - 1, s = 0;
while ((d & 1) == 0) {
d >>= 1;
++s;
}
auto witness = [&](u64 a) {
u64 x = mod_pow(a % n, d, n);
if (x == 1 || x == n - 1) return false;
for (u64 r = 1; r < s; ++r) {
x = mod_mul(x, x, n);
if (x == n - 1) return false;
}
return true;
};
for (u64 a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
if (a % n != 0 && witness(a)) return false;
}
return true;
}
u64 pollard_rho(u64 n) {
if ((n & 1) == 0) return 2;
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
while (true) {
u64 c = uniform_int_distribution<u64>(1, n - 1)(rng);
u64 x = uniform_int_distribution<u64>(0, n - 1)(rng);
u64 y = x;
u64 d = 1;
auto f = [&](u64 v) {
return (mod_mul(v, v, n) + c) % n;
};
while (d == 1) {
x = f(x);
y = f(f(y));
u64 diff = x > y ? x - y : y - x;
d = gcd_u64(diff, n);
}
if (d != n) return d;
}
}
void factor_rec(u64 n, vector<u64>& factors) {
if (n == 1) return;
if (is_prime(n)) {
factors.push_back(n);
return;
}
u64 d = pollard_rho(n);
factor_rec(d, factors);
factor_rec(n / d, factors);
}
vector<u64> factorize_u64(u64 n) {
vector<u64> factors;
factor_rec(n, factors);
sort(factors.begin(), factors.end());
return factors;
}
// Example application: largest prime factor of a 64-bit integer.
u64 largest_prime_factor(u64 n) {
vector<u64> factors = factorize_u64(n);
return factors.empty() ? 0 : factors.back();
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.