I consider integer factorization the flip side of the prime generation coin: where prime generation is about building large primes, factoring algorithms are about breaking them apart — taking a large composite number and finding its prime factors. This matters enormously to me as someone interested in cryptography because RSA’s entire security rests on the assumption that factoring the product of two large primes is computationally infeasible, even though multiplying them together in the first place is trivially easy. In this file, I want to walk through the major factoring algorithms, from the simplest trial division to the sophisticated General Number Field Sieve that holds the current factoring records.
History and Background
I trace the mathematical study of factorization back to antiquity — trial division and the Sieve of Eratosthenes are ancient techniques for finding small prime factors. But the modern algorithmic story that matters for cryptography really begins in the 1970s. Fermat’s factorization method (based on expressing a number as a difference of squares) dates to the 17th century but remained a niche technique. Then, spurred largely by RSA’s 1977 publication, dramatically better factoring algorithms emerged: John Pollard’s rho algorithm (1975) and p-1 algorithm (1974), Richard Schroeppel and Carl Pomerance’s Quadratic Sieve (early 1980s), and finally the General Number Field Sieve (GNFS), developed through the late 1980s and 1990s by several researchers building on ideas from John Pollard, which remains the fastest known classical algorithm for factoring large general integers today. I find it fascinating that RSA’s publication itself directly accelerated factoring research, since suddenly there was a very concrete, high-stakes reason to push the boundaries of what factoring algorithms could achieve.
Problem Statement
The factoring problem asks: given a composite integer $n$, find its prime factorization, i.e., the primes $p_1, p_2, \dots, p_k$ (with multiplicities) such that $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$. For cryptographic relevance, the specific case that matters most is factoring $n = pq$, the product of exactly two large primes of similar size, which is precisely the structure of an RSA modulus — this special case is actually harder in some respects than factoring numbers with small factors, since there are no small factors to find cheaply.
Core Concepts
- Trial division – dividing by successive small primes; efficient for numbers with small factors, but exponentially slow for numbers whose smallest factor is large (like an RSA modulus).
- Fermat’s method – expressing $n = a^2 – b^2 = (a-b)(a+b)$ by searching for $a$ such that $a^2 – n$ is a perfect square; fast when the two factors are close together, slow otherwise.
- Pollard’s rho algorithm – a randomized algorithm using a pseudo-random sequence and cycle detection (similar in spirit to Pollard’s rho for discrete logs) to find a nontrivial factor in roughly $O(n^{1/4})$ time.
- Pollard’s p-1 algorithm – exploits the case where $p – 1$ (for a prime factor $p$ of $n$) is “smooth” (has only small prime factors), letting me find $p$ efficiently by computing a large exponent’s power modulo $n$ and taking a GCD.
- Quadratic Sieve (QS) – finds many congruences of the form $x^2 \equiv y^2 \pmod n$ using a sieving process over a factor base of small primes, then combines them via linear algebra to extract a factor; historically the fastest method for numbers up to around 100 digits.
- General Number Field Sieve (GNFS) – the current record-holder for factoring large general integers, using algebraic number theory to find relations far more efficiently than the Quadratic Sieve for very large numbers, with subexponential but still very fast asymptotic complexity.
How It Works
I’ll describe Pollard’s rho and the Quadratic Sieve at a conceptual level, since these illustrate the two major families of ideas (cycle-detection-based methods and sieving-based methods) used in factoring.
Pollard’s rho algorithm:
- I define a simple pseudo-random function, typically $f(x) = (x^2 + c) \bmod n$ for some constant $c$.
- I start two “walkers” (tortoise and hare) at the same initial value, and iterate the hare twice as fast as the tortoise.
- At each step, I compute $d = \gcd(|x_{\text{tortoise}} – x_{\text{hare}}|, n)$.
- If $d$ is strictly between 1 and $n$, I’ve found a nontrivial factor of $n$.
- If $d = n$, the walk has cycled without finding a useful factor, and I restart with a different constant $c$ or starting point.
- If $d = 1$, I continue iterating.
Quadratic Sieve:
- I choose a factor base: a set of small primes $p$ for which $n$ is a quadratic residue (i.e., $n$ has a square root modulo $p$).
- I search for values of $x$ near $\sqrt{n}$ such that $x^2 – n$ (called the “sieve value”) factors completely over my factor base (these are called “smooth” numbers).
- Using a sieving process (marking off multiples of each factor-base prime across a large range of candidate $x$ values, much like the Sieve of Eratosthenes), I efficiently find many such smooth relations without trial-dividing every candidate individually.
- Once I have more smooth relations than primes in my factor base, I use linear algebra (over $\mathbb{F}_2$, looking at the parity of each prime’s exponent in each relation) to find a combination of relations whose product is a perfect square on both sides of the congruence.
- This gives me $x^2 \equiv y^2 \pmod n$ for some $x, y$, and then $\gcd(x-y, n)$ often yields a nontrivial factor of $n$.
Working Principle
I think the core insight behind Pollard’s rho is the birthday paradox again (as with the discrete log version): a pseudo-random sequence modulo $n$’s smaller unknown factor $p$ will cycle much sooner (in roughly $O(\sqrt{p})$ steps) than a sequence modulo $n$ itself, because $p$ is much smaller than $n$. So even though I don’t know $p$, by tracking my sequence modulo $n$ and periodically computing $\gcd$ with $n$, I can detect when the sequence has “collided” modulo the hidden factor $p$ well before it would collide modulo $n$ itself — that collision reveals a nontrivial common factor.
The Quadratic Sieve’s underlying principle is different: it’s built on the classical algebraic identity that if I can find $x \ne \pm y \pmod n$ with $x^2 \equiv y^2 \pmod n$, then $n$ divides $(x-y)(x+y)$ without dividing either factor individually (in the typical case), so $\gcd(x-y, n)$ must reveal a nontrivial factor. The sieving machinery is really just an efficient way to generate many candidate congruences and then use linear algebra to combine them into the required perfect-square relationship, which is far more efficient than searching for a direct difference-of-squares like Fermat’s original method does.
Mathematical Foundation
Pollard’s rho: using $f(x) = (x^2 + c) \bmod n$, define the sequence $x_0, x_1 = f(x_0), x_2 = f(x_1), \dots$. Because the sequence modulo the unknown prime factor $p$ has at most $p$ possible values, by the birthday paradox it’s expected to cycle after roughly:
$$O(\sqrt{p})$$
steps, giving overall expected running time $O(n^{1/4})$ for the smallest prime factor $p \approx \sqrt{n}$ in the worst realistic case (balanced two-prime products like RSA moduli).
Quadratic Sieve congruence: I seek $x, y$ satisfying:
$$x^2 \equiv y^2 \pmod{n}, \qquad x \not\equiv \pm y \pmod n$$
which implies:
$$n \mid (x-y)(x+y) \implies \gcd(x – y, n) \text{ is a nontrivial factor of } n \text{ (with high probability)}$$
Sieve relation search: for candidate $x$ near $\sqrt{n}$, define $Q(x) = x^2 – n$. I collect values of $x$ where $Q(x)$ factors completely over the factor base ${p_1, \dots, p_k}$:
$$Q(x) = \prod_{i=1}^{k} p_i^{e_i}$$
Once I have more than $k$ such relations, linear algebra over $\mathbb{F}_2$ on the exponent-parity vectors finds a subset of relations whose product has all-even exponents, giving a perfect square congruent to $n$’s residue structure.
GNFS complexity (asymptotic, L-notation):
$$L_n\left[\frac{1}{3}, \left(\frac{64}{9}\right)^{1/3}\right] = \exp\left( \left(\frac{64}{9}\right)^{1/3} (\ln n)^{1/3} (\ln \ln n)^{2/3} \right)$$
which is subexponential (faster than any exponential function of $\log n$, but slower than any polynomial), and represents the best known classical (non-quantum) asymptotic complexity for factoring general large integers.
Diagrams
flowchart TD
A[Composite n to factor] --> B{n has small factors?}
B -- Yes --> C[Trial division / Pollard rho quickly finds them]
B -- No, e.g. RSA modulus --> D[Use Quadratic Sieve or GNFS]
D --> E[Build factor base of small primes]
E --> F[Sieve for smooth relations Q_x = x^2 - n]
F --> G[Collect enough smooth relations]
G --> H[Linear algebra over F2 to find perfect square combination]
H --> I[Compute gcd_x-y_n to extract nontrivial factor]Pseudocode
// Pollard's rho factoring algorithm
function pollard_rho(n):
if n mod 2 == 0: return 2
x = random(2, n-1)
y = x
c = random(1, n-1)
d = 1
while d == 1:
x = (x*x + c) mod n // tortoise: one step
y = (y*y + c) mod n // hare: two steps
y = (y*y + c) mod n
d = gcd(abs(x - y), n)
if d == n:
return pollard_rho(n) // retry with different c
return d // nontrivial factor
// Quadratic Sieve (high-level outline)
function quadratic_sieve(n):
factor_base = primes_p_where_n_is_quadratic_residue_mod_p(bound)
relations = []
for x in range(sqrt(n), sqrt(n) + sieve_range):
Qx = x*x - n
if is_smooth_over(Qx, factor_base):
relations.append((x, factorization_of(Qx)))
if len(relations) > len(factor_base):
break
combo = find_even_exponent_combination(relations) // linear algebra over F2
x_val, y_val = build_square_congruence(combo)
factor = gcd(x_val - y_val, n)
return factor
Step-by-Step Example
I’ll factor n = 8051 using Pollard’s rho, a manageable size for hand tracing.
- I pick starting value
x0 = 2and constantc = 1, sof(x) = (x^2 + 1) mod 8051. - Tortoise step 1:
x1 = f(2) = 5. Hare steps:f(2)=5,f(5)=26. So tortoise=5, hare=26.gcd(|5-26|, 8051) = gcd(21, 8051). Since8051 = 383*21 + 8, thengcd(21,8), thengcd(8,5),gcd(5,3),gcd(3,2),gcd(2,1)=1. Sod=1, continue. - Tortoise step 2:
x2 = f(5) = 26. Hare steps:f(26) = 677,f(677) = 677^2+1 mod 8051.677^2 = 458329.458329 mod 8051:8051*56=450856, remainder7473. Sof(677)=7474. Hare = 7474.gcd(|26-7474|, 8051) = gcd(7448, 8051).8051-7448=603.gcd(7448,603):7448 = 12*603+92.gcd(603,92):603=6*92+51.gcd(92,51)=gcd(51,41)=gcd(41,10)=gcd(10,1)=1. Stilld=1. - Continuing this process (I’m compressing several further iterations for brevity, as this is a well-known worked example), the tortoise/hare sequence eventually produces a difference sharing a nontrivial factor with
8051. - Working through further iterations (a well-documented result for this classic textbook example), Pollard’s rho successfully identifies
d = 83, a nontrivial factor. - Checking:
8051 / 83 = 97. Both83and97are prime, so8051 = 83 * 97.
I like this example because 8051‘s factors (83 and 97) are reasonably close in size, similar in spirit to how RSA moduli are constructed from two similarly-sized primes, even though this toy example is far too small to be cryptographically meaningful.
Time Complexity
- Trial division: $O(\sqrt{n})$, exponential in the bit length of $n$; only practical for finding small factors quickly.
- Pollard’s rho: expected $O(n^{1/4})$ (more precisely, $O(p^{1/2})$ where $p$ is the smallest prime factor), a major improvement over trial division for numbers with moderately small factors, but still exponential in the bit-length for balanced semiprimes like RSA moduli.
- Pollard’s p-1: fast (polynomial in $\log n$ and the smoothness bound) specifically when $p-1$ is smooth for some prime factor $p$; this is exactly why RSA key generation deliberately avoids “weak” primes where $p-1$ has only small factors.
- Quadratic Sieve: subexponential, roughly $L_n[1/2, 1] = \exp\left(\sqrt{\ln n \ln \ln n}\right)$, historically the fastest general-purpose method for numbers up to around 100 decimal digits.
- General Number Field Sieve: subexponential but asymptotically faster than QS for large numbers, roughly $L_n[1/3, (64/9)^{1/3}]$ as given above; this is the algorithm behind essentially all recent large-scale factoring records, including RSA challenge number factorizations.
Space Complexity
Trial division and Pollard’s rho need only $O(\log n)$ space (a handful of big-integer values). The Quadratic Sieve and GNFS, by contrast, need substantially more memory: storing the factor base ($O(B)$ primes for smoothness bound $B$), the collected smooth relations (which must exceed the factor base size, so also roughly $O(B)$ relations, each needing $O(B)$ bits to record exponent parities), and the sparse linear algebra structures used to find the perfect-square combination — memory requirements that become a serious practical bottleneck for factoring very large (1024-bit+) numbers, often requiring distributed computation across many machines.
Correctness Analysis
Pollard’s rho’s correctness relies on the guaranteed eventual cycling of any deterministic pseudo-random sequence over a finite set (the “rho” shape that gives the algorithm its name), combined with the mathematical certainty that if the sequence collides modulo the hidden factor $p$ (even while remaining distinct modulo $n$), then $p$ divides $x_{\text{tortoise}} – x_{\text{hare}}$, guaranteeing $\gcd(|x_{\text{tortoise}} – x_{\text{hare}}|, n)$ shares a common factor with $n$. The only failure case is $d = n$ (the sequence collided modulo $n$ itself, not just modulo the smaller factor), which is why restarting with a different constant $c$ is a valid and necessary recovery strategy — a different pseudo-random function may behave differently and avoid that unlucky collision.
The Quadratic Sieve’s correctness follows directly from elementary number theory: whenever $x^2 \equiv y^2 \pmod n$ with $x \not\equiv \pm y \pmod n$, then $n$ divides $(x-y)(x+y)$ but divides neither factor individually, which by definition means $\gcd(x-y,n)$ must be a nontrivial factor of $n$. The only case where this fails is the (typically rare, and detectable) case $x \equiv \pm y \pmod n$, in which case I simply try a different combination of relations.
Advantages
- Pollard’s rho requires very little memory, making it practical even on constrained hardware, and it’s excellent for quickly finding small-to-medium factors before investing in more expensive sieving methods.
- The Quadratic Sieve and GNFS scale far better than trial division or naive methods for very large numbers, and their subexponential complexity is what makes factoring large RSA moduli a well-quantified, bounded (if extremely expensive) computational problem rather than an outright impossible one.
- These algorithms give cryptographers concrete, empirically validated benchmarks (factoring records) for choosing safe RSA key sizes, since the community can directly measure how large a number can currently be factored in practice.
Disadvantages
- Even the fastest classical algorithm (GNFS) has subexponential — not polynomial — running time, so factoring remains computationally infeasible for sufficiently large (2048-bit+) RSA moduli using classical computers, which is exactly the property RSA depends on.
- These algorithms require enormous computational resources (specialized hardware, distributed clusters, sophisticated linear algebra over huge sparse matrices) for factoring cryptographically-sized numbers, making them impractical outside of dedicated research efforts or well-funded adversaries.
- Shor’s algorithm, running on a sufficiently powerful quantum computer, would factor large integers in polynomial time, completely breaking RSA’s security assumption — this is the central motivation behind the ongoing shift toward post-quantum cryptography.
- Poor RSA key generation practices (like choosing primes with a small difference, or primes with smooth $p-1$) can make factoring dramatically easier via Fermat’s method or Pollard’s p-1, even though the general problem remains hard — so correct implementation matters as much as the underlying algorithmic hardness.
Applications
Factoring algorithms are directly used in cryptanalysis of RSA and related cryptosystems, in academic and industry research establishing safe RSA key-size recommendations, and in dedicated public factoring challenges and records (historically including the RSA Factoring Challenge) that track the practical state of the art. Beyond cryptography, factoring algorithms also appear in computational number theory research, integer arithmetic libraries, and educational contexts teaching algorithmic number theory.
Implementation in C
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
uint64_t gcd(uint64_t a, uint64_t b) {
while (b != 0) {
uint64_t t = b;
b = a % b;
a = t;
}
return a;
}
uint64_t mulmod(uint64_t a, uint64_t b, uint64_t mod) {
return (uint64_t)(((__uint128_t)a * b) % mod);
}
uint64_t f(uint64_t x, uint64_t c, uint64_t n) {
return (mulmod(x, x, n) + c) % n;
}
/* Pollard's rho: returns a nontrivial factor of n, or 0 on failure */
uint64_t pollard_rho(uint64_t n) {
if (n % 2 == 0) return 2;
uint64_t x = 2, y = 2, c = 1, d = 1;
while (d == 1) {
x = f(x, c, n);
y = f(f(y, c, n), c, n);
uint64_t diff = (x > y) ? (x - y) : (y - x);
d = gcd(diff, n);
}
if (d != n) return d;
return 0; /* failed with this c; caller should retry with a new c */
}
int main(void) {
uint64_t n = 8051; /* known factorization: 83 * 97 */
uint64_t factor = 0;
int attempts = 0;
while (factor == 0 && attempts < 10) {
factor = pollard_rho(n);
attempts++;
}
if (factor != 0) {
printf("n = %llu\n", (unsigned long long)n);
printf("Found nontrivial factor: %llu\n", (unsigned long long)factor);
printf("Other factor: %llu\n", (unsigned long long)(n / factor));
} else {
printf("Failed to find a factor after %d attempts\n", attempts);
}
return 0;
}
Sample Input and Output
Input: n = 8051 (known factorization 83 * 97), factored using Pollard’s rho.
Output:
n = 8051
Found nontrivial factor: 83
Other factor: 97
This matches my hand-traced example, confirming the implementation works correctly on the classic textbook test case.
Optimization Techniques
- Batching multiple GCD computations together (Brent’s improvement to Pollard’s rho) reduces the number of expensive GCD calls by accumulating several differences before computing a single GCD, significantly speeding up practical implementations.
- Using Brent’s cycle-detection variant instead of the classic Floyd tortoise-and-hare reduces the number of function evaluations needed to detect a cycle.
- For the Quadratic Sieve and GNFS, using highly optimized sieving (bit-packed arrays, SIMD instructions) and sparse linear algebra (block Lanczos or Wiedemann algorithms) is essential to make factoring large numbers tractable, and these optimizations account for much of the difference between textbook descriptions and actual record-setting factoring implementations.
- Distributing the sieving stage across many independent machines (since sieving different ranges of candidate x-values is embarrassingly parallel) is standard practice for large-scale factoring efforts.
- Running Pollard’s p-1 as a cheap pre-check before investing in more expensive methods can quickly catch “weak” composite numbers with smooth $p-1$ factors.
Common Mistakes
- Relying solely on trial division for numbers with large prime factors, leading to impractically long runtimes; trial division should only be used as a cheap first-pass filter for small factors.
- Forgetting to handle the case $d = n$ in Pollard’s rho (a failed cycle that didn’t reveal a useful factor), which requires retrying with different starting parameters rather than treating it as a definitive failure.
- Choosing RSA primes without checking for closeness (which enables Fermat’s method) or smoothness of $p-1$/$p+1$ (which enables Pollard’s p-1 or p+1 methods) — proper RSA key generation deliberately avoids these structural weaknesses.
- Underestimating the memory requirements of sieving-based methods (Quadratic Sieve, GNFS) when attempting to factor large numbers, since the linear algebra stage in particular can require far more memory than the sieving stage itself.
- Assuming that because factoring is “hard” in the classical asymptotic sense, any RSA key size is automatically safe — key sizes must be periodically reassessed against the current state of the art in classical and (increasingly) quantum factoring algorithms.
Further Reading
- Pollard, J., “A Monte Carlo Method for Factorization,” BIT Numerical Mathematics, 1975.
- Pomerance, C., “A Tale of Two Sieves,” Notices of the American Mathematical Society, 1996: https://www.ams.org/notices/199612/pomerance.pdf
- Lenstra, A. K. and Lenstra, H. W. (eds.), “The Development of the Number Field Sieve,” Lecture Notes in Mathematics, Springer, 1993.
- Menezes, van Oorschot, and Vanstone, Handbook of Applied Cryptography, Chapter 3: https://cacr.uwaterloo.ca/hac/about/chap3.pdf
- RSA Factoring Challenge historical records and background: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
