Two sides, two factor bases, one square
The number field sieve seeks a congruence of squares as every general method does, but manufactures it using a number field. Choose a polynomial with a root modulo n; then pairs (a, b) give a rational value and an algebraic norm, and pairs smooth on both sides give relations. Combining them yields a square in ℤ and a square in the number field, whose images agree modulo n. The complexity drops to L[1/3] — a genuine change of exponent, not a constant-factor improvement.
Learning objectives
- Outline the five stages of the number field sieve.
- Explain what polynomial selection optimises.
- Describe the two factor bases and the need for character columns.
- Explain the square root step and why it is difficult.
- Distinguish the special from the general number field sieve.
Section 01The structure
- Stage 01Polynomial selectionChoose f of degree d with a root m modulo n, and the linear g(x) = x − m. Small coefficients and good root properties matter enormously.
- Stage 02SievingFor pairs (a, b), test whether a − bm is smooth over the rational factor base and bdf(a/b) is smooth over the algebraic factor base.
- Stage 03FilteringRemove singletons, merge relations, find cycles among large primes, and reduce the matrix before solving.
- Stage 04Linear algebraFind a kernel vector over GF(2) using Block Lanczos or Block Wiedemann.
- Stage 05Square rootCompute a square root of a large product in the number field and map it to ℤ/n, then take a GCD.
A single side would just be the quadratic sieve. Using two polynomials with a common root modulo n means the values to be tested for smoothness are much smaller than those in the quadratic sieve, which is what changes the exponent from 1/2 to 1/3.
Section 02Polynomial selection
The choice of f dominates the total running time — a better polynomial can halve the sieving effort. Two properties are optimised together.
| Property | Measure | Why it matters |
|---|---|---|
| Size | Magnitude of the norms over the sieving region | Smaller norms are more likely to be smooth |
| Root properties | The alpha value, measuring extra divisibility by small primes | A polynomial with many roots modulo small primes yields systematically smoother values |
| Skewness | Aspect ratio of the sieving region | Allows the region to be shaped to where the norms are smallest |
For record factorisations, polynomial selection consumes a significant fraction of the total effort before sieving begins — and it repays that investment several times over. Searching millions of candidates and ranking them by the measures above is standard practice.
Section 03Factor bases and characters
The rational side uses ordinary primes. The algebraic side uses prime ideals of the number field, represented as pairs (p, r) where r is a root of f modulo p — that is, the degree-one primes above p.
A product of algebraic numbers whose norms multiply to a square need not itself be a square: units and the class group obstruct the implication. Quadratic character columns are appended to the matrix to force the product into the subgroup of squares, and omitting them yields a kernel vector that fails at the square root step for no visible reason.
This is the point at which the algorithm genuinely requires algebraic number theory: the unit group and class group of the number field intervene, and the character columns are the practical device that neutralises them.
Section 04The square root step and SNFS
The final stage must compute a square root of an algebraic number represented as a product of millions of small elements, whose expanded form would have astronomically many digits. It is done modulo many primes with reconstruction by the Chinese remainder theorem, or by Couveignes's method exploiting the structure of the product.
For numbers of the form re ± s with small r and s, an excellent polynomial is available immediately. The smaller constant makes SNFS applicable to considerably larger numbers of that shape.
For arbitrary n, the polynomial must be searched for. This is the algorithm that sets records for RSA-type moduli and against which key sizes are calibrated.
NFS is far harder to implement correctly than MPQS: polynomial selection, filtering, sparse linear algebra and the algebraic square root are each substantial subsystems. Below about 100 digits the quadratic sieve is both faster and vastly simpler, and reaching for NFS early is a common misjudgement.
ReferenceFrequently asked questions
Why is the complexity exponent 1/3 rather than 1/2?
Because the two-sided construction produces values to be tested for smoothness that are much smaller relative to n than the single-sided quadratic sieve's. Optimising the resulting smoothness probabilities against the factor base size gives the exponent 1/3.
What makes a number amenable to SNFS?
A representation as a small polynomial evaluated at a small argument — typically the form r^e ± s. Cunningham numbers are the classic family. RSA moduli have no such form, which is precisely why they require the general algorithm.
Do quantum computers change this picture?
Shor's algorithm factors in polynomial time on a sufficiently large fault-tolerant quantum computer, which would render all of this obsolete for cryptographic purposes. No such machine exists at the scale required, and the classical algorithms above remain the state of the art in practice.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.