Integer Factorization
Several algorithms factor integers — some are fast on “nice” inputs and painfully slow on others.
Important: if n is prime, Fermat / Pollard p−1 / Pollard ρ tend to crawl. Run a fast primality test first.
This lesson follows CP-Algorithms — Integer factorization.
Trial division — O(√n)
At least one prime factor of a composite n is ≤ √n. Test d = 2 … ⌊√n⌋, peel factors, and if nothing divides, n itself is prime.
vector<long long> trial_division1(long long n) {
vector<long long> factorization;
for (long long d = 2; d * d <= n; d++) {
while (n % d == 0) {
factorization.push_back(d);
n /= d;
}
}
if (n > 1)
factorization.push_back(n);
return factorization;
}
Pseudo-polynomial: polynomial in the value of n, exponential in the bit-length.
Wheel factorization
Skip even d after removing factors of 2 (~50% fewer checks):
vector<long long> trial_division2(long long n) {
vector<long long> factorization;
while (n % 2 == 0) {
factorization.push_back(2);
n /= 2;
}
for (long long d = 3; d * d <= n; d += 2) {
while (n % d == 0) {
factorization.push_back(d);
n /= d;
}
}
if (n > 1)
factorization.push_back(n);
return factorization;
}
After removing 2 and 3, only residues 1 and 5 mod 6 remain (~33%). Extending to primes {2,3,5} uses a stride table:
vector<long long> trial_division3(long long n) {
vector<long long> factorization;
for (int d : {2, 3, 5}) {
while (n % d == 0) {
factorization.push_back(d);
n /= d;
}
}
static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
int i = 0;
for (long long d = 7; d * d <= n; d += increments[i++]) {
while (n % d == 0) {
factorization.push_back(d);
n /= d;
}
if (i == 8)
i = 0;
}
if (n > 1)
factorization.push_back(n);
return factorization;
}
Precomputed primes
Ultimate wheel: sieve primes up to √n and only try those.
vector<long long> primes; // filled by sieve up to sqrt(max n)
vector<long long> trial_division4(long long n) {
vector<long long> factorization;
for (long long d : primes) {
if (d * d > n)
break;
while (n % d == 0) {
factorization.push_back(d);
n /= d;
}
}
if (n > 1)
factorization.push_back(n);
return factorization;
}
🧪 Trial division + 2/3/5 wheel on 123456789
Fermat’s method
Odd composite n = p·q is a difference of squares:
n = ((p+q)/2)² − ((p−q)/2)²
Guess a ≥ ceil(√n) until a² − n = b², then factors are a−b and a+b. Runtime O(|p−q|) — great when factors are close, terrible when they are far. Rarely the first tool in practice (though modular filters on possible a help a bit).
int fermat(int n) {
int a = ceil(sqrt(n));
int b2 = a * a - n;
int b = round(sqrt(b2));
while (b * b != b2) {
a = a + 1;
b2 = a * a - n;
b = round(sqrt(b2));
}
return a - b;
}
Pollard’s p − 1
Often some prime factor p has p−1 B-powersmooth (every prime-power factor ≤ B) for modest B.
By Fermat’s little theorem, if p−1 | M then aᴹ ≡ 1 (mod p), so p | gcd(aᴹ − 1, n).
Take M = lcm(1…B) (equivalently product of maximal prime powers ≤ B). Raise a random a to those powers mod n, computing gcd along the way. Grow B if needed.
Complexity ~ O(B log B log² n) per iteration; probabilistic — may fail to find a factor.
// needs: primes[], power(a,e,mod), gcd
long long pollards_p_minus_1(long long n) {
int B = 10;
long long g = 1;
while (B <= 1000000 && g < n) {
long long a = 2 + rand() % (n - 3);
g = gcd(a, n);
if (g > 1)
return g;
for (int p : primes) {
if (p >= B) continue;
long long p_power = 1;
while (p_power * p <= B)
p_power *= p;
a = power(a, p_power, n);
g = gcd(a - 1, n);
if (g > 1 && g < n)
return g;
}
B *= 2;
}
return 1;
}
Pollard’s ρ
Let n = p·q. Walk a polynomial sequence xᵢ₊₁ = f(xᵢ) mod n, usually f(x) = x² + c. The sequence mod p lives in a small set and forms a ρ-shaped cycle after expected O(√p) steps (O(n¹ᐟ⁴) if p ≤ √n).
A collision xₛ ≡ xₜ (mod p) means p | gcd(|xₛ − xₜ|, n) — without knowing p.
Floyd (tortoise & hare)
One pointer advances once per step, the other twice. Meet in O(λ + μ). Overall Pollard ρ with Floyd: about O(n¹ᐟ⁴ log n).
long long mult(long long a, long long b, long long mod) {
long long result = 0;
while (b) {
if (b & 1)
result = (result + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return result;
}
long long f(long long x, long long c, long long mod) {
return (mult(x, x, mod) + c) % mod;
}
long long rho(long long n, long long x0 = 2, long long c = 1) {
long long x = x0, y = x0, g = 1;
while (g == 1) {
x = f(x, c, n);
y = f(y, c, n);
y = f(y, c, n);
g = abs(x - y);
// gcd below
long long a = g, b = n;
while (b) { long long t = a % b; a = b; b = t; }
g = a;
}
return g;
}
If the algorithm returns n, retry with different x₀ / c (e.g. 25 fails for x₀=c=1 but factors with c=2).
🧪 Pollard ρ on 2206637
Brent’s cycle detection
Advance the hare in power-of-two blocks. Same asymptotics, fewer f evaluations. Batch gcd every m steps (multiply differences, backtrack if gcd = n).
long long brent(long long n, long long x0 = 2, long long c = 1) {
long long x = x0, g = 1, q = 1, xs = 0, y = 0;
int m = 128, l = 1;
while (g == 1) {
y = x;
for (int i = 1; i < l; i++)
x = f(x, c, n);
int k = 0;
while (k < l && g == 1) {
xs = x;
for (int i = 0; i < m && i < l - k; i++) {
x = f(x, c, n);
q = mult(q, abs(y - x), n);
}
g = gcdll(q, n);
k += m;
}
l *= 2;
}
if (g == n) {
do {
xs = f(xs, c, n);
g = gcdll(xs - y, n);
} while (g == 1);
}
return g;
}
Practical combo: trial-divide small primes, then Brent–Pollard ρ on the cofactor.
Interactive walkthrough
Check: trial & Fermat
Trial division and Fermat
1 / 4Why only test d up to √n in trial division?
Pick an answer to see if you are right.
Check: Pollard methods
Pollard p−1 and ρ
1 / 4Pollard p−1 targets factors p where…
Pick an answer to see if you are right.
Practice drills
Read n. Print prime factors in non-decreasing order separated by spaces (with multiplicity).
Contest problems
From CP-Algorithms:
Small primes by trial / wheel; hard cofactors with Brent–Pollard ρ (+ primality test).
Cheat sheet
| Method | When | Cost (typical) |
|---|---|---|
| Trial / wheel | Small n or small factors | O(√n) / better constants |
| Sieve primes | Many factorizations | Precompute + trial primes |
| Fermat | p ≈ q | `O( |
Pollard p−1 | p−1 smooth | Depends on B |
| Pollard ρ / Brent | General hard composites | ~O(n¹ᐟ⁴ log n) |
| Pipeline | Always | Primality → trial small → ρ |