Engineering / Mathematics — Discrete Logarithms and Factoring
Subexponential Integer Factoring
Factoring by congruences of squares, the relation collection and linear algebra phases, and the resulting subexponential cost.
Executive summary
Modern factoring algorithms all work by finding two numbers whose squares are congruent modulo n but which are not themselves congruent. A gcd then splits the modulus.
Finding such a pair is done by collecting smooth relations and solving a linear system over the field of two elements.
Learning objectives
- State the congruence of squares principle.
- Describe relation collection and the linear algebra step.
- State the success probability per dependency.
01Congruences of squares
Splitting by a congruence of squares
If x² ≡ y² (mod n) but x ≢ ±y (mod n), then gcd(x − y, n) is a proper factor of n.
Reason. n divides (x−y)(x+y) but divides neither factor, so its prime factors are distributed between them.
The condition x ≢ ±y is essential and is where the probabilistic element enters. For a modulus with two distinct prime factors, a random square root of a square is congruent to ±y half the time, so each dependency succeeds with probability at least one half.
02Relation collection
The problem becomes constructing such a pair. The approach is to find many values whose squares reduce to smooth numbers modulo n, then combine them so the product is a perfect square.
Fix a factor base
Primes up to a smoothness bound, chosen from the density analysis.
Generate candidates
Values near √n whose squares reduce to small residues, tested for smoothness by sieving.
Record exponent vectors
Each smooth relation gives a vector of prime exponents, reduced modulo 2.
Find a dependency
Once there are more relations than factor base primes, a linear dependence over GF(2) exists.
Form the congruence
Multiplying the relations in a dependency gives a product where every exponent is even — a perfect square.
Reducing exponents modulo 2 is the key simplification: only the parity matters, because a product is a square exactly when every exponent is even. The linear algebra is therefore over the two-element field, which makes it fast despite the matrix size.
03Cost and the two bottlenecks
- Relation collection
Dominant, highly parallelEach candidate independent; scales across machines - Linear algebra
Large sparse system over GF(2)Hard to parallelise; often the practical bottleneck - Square root and gcd
NegligibleOne square root computation and a gcd per dependency
| Algorithm | Complexity | Practical range |
|---|---|---|
| Quadratic sieve | L(1/2, 1) | Best up to about 100 digits |
| Number field sieve | L(1/3, 1.92) | Best beyond that; used for all records |
Relation collection parallelises almost perfectly, which is why factoring records are set by large distributed efforts. The linear algebra phase does not, and it typically requires a single large machine with substantial memory, making it the harder half to scale.
Each dependency yields a factorisation with probability at least one half, so collecting a few extra relations beyond the minimum ensures success without materially increasing cost.
04Frequently asked questions
Why reduce exponents modulo 2?
Because the goal is a perfect square, which requires only that every exponent be even. Working modulo 2 discards irrelevant information and reduces the linear algebra to the smallest possible field.
What if a dependency gives x ≡ ±y?
The attempt fails and another dependency is tried. Since each succeeds with probability at least one half, a handful of extra relations makes overall failure negligible.
Why is the number field sieve better?
It generates relations from algebraic number fields where the values involved are much smaller, so smooth values are far more common. That improves the exponent from 1/2 to 1/3, which is an enormous gain at large sizes.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 344-352.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.