Engineering / Mathematics — Discrete Logarithms and Factoring
The Number Field Sieve and Factoring Records
The number field sieve, the current state of factoring records, and how key size recommendations follow from them.
Executive summary
The number field sieve is the fastest known general factoring algorithm and the basis of every record. It generates relations in an algebraic number field where the relevant values are much smaller.
Records and key size recommendations move over time, so this page routes to live authoritative sources rather than reproducing figures with a shelf life.
Learning objectives
- Describe the structure of the number field sieve.
- Explain how key size recommendations are derived.
- Locate current authoritative figures.
01Structure of the algorithm
Polynomial selection
Search for a polynomial with a root modulo n and good smoothness properties. A substantial share of total effort.
Sieving
Collect relations that are smooth on both the rational and algebraic sides simultaneously.
Filtering
Reduce the relation set, merging partial relations and removing singletons before the linear algebra.
Linear algebra
Find dependencies in a very large sparse matrix over GF(2), using block Lanczos or block Wiedemann.
Square root
Compute an algebraic square root and derive the congruence of squares, then take a gcd.
The gain over the quadratic sieve comes from the values being sieved being much smaller, which raises the smoothness rate enough to improve the exponent from 1/2 to 1/3.
L_n(1/3, 1.92) = exp((1.92 + o(1))(ln n)^{1/3}(ln ln n)^{2/3})02From records to key sizes
Key size recommendations are extrapolations from record computations, adjusted for expected improvements in hardware and algorithms over the intended lifetime of the key.
Measure a record
A completed factorisation gives a concrete effort figure in core-years for a specific modulus size.
Extrapolate by the complexity formula
The L(1/3) expression predicts effort at other sizes.
Add a margin
Allow for hardware improvement and possible algorithmic advances over the key's lifetime.
Publish a recommendation
Standards bodies convert this into minimum key sizes by protection period.
03Live sources rather than transcribed figures
Standards bodies
National and international standards organisations publish key length recommendations by protection period and revise them periodically.
Key length comparison sites
Several maintained services aggregate the recommendations of different bodies side by side.
Record announcements
Factoring records are announced by the teams involved with full effort accounting, which is the primary source for extrapolation.
Post-quantum guidance
Migration timelines are published separately and are moving faster than classical key size guidance.
The durable content is the method: how the algorithm works, why the complexity has the form it does, and how a recommendation is derived from a record. Those do not change. The numbers do, and should be read from a maintained source at the time of use.
04Frequently asked questions
Why is polynomial selection so important?
Because the polynomial determines the size and smoothness behaviour of every value sieved afterwards. A better polynomial improves the yield across the entire sieving phase, so a large search up front pays back many times over.
Is the linear algebra step the bottleneck?
Often, in practice. Sieving parallelises across many machines; the sparse linear algebra does not parallelise nearly as well and typically requires a single large machine with substantial memory.
Would a quantum computer change this?
Fundamentally. Shor's algorithm factors in polynomial time on a sufficiently large fault-tolerant quantum computer, which would break RSA outright rather than merely requiring larger keys. This is what drives post-quantum migration.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 356-358.
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.
Forward reference: this page extends beyond the source text and is flagged as post-source.
Author: Kevin Jogin. Last reviewed 2026-08-07.