Engineering/Mathematics/Algorithm engineering

Subexponential Factoring and Index Calculus

Every subexponential attack on RSA and prime-field Diffie–Hellman follows the same three-act structure: collect relations over a factor base, solve a huge sparse linear system, and turn the answer into a factor or a logarithm. Smooth-number density sets every parameter in it.

Advanced algorithm
Computing
Sets key sizes
≈18 min read
Basis of RSA security margins

L_n[½, 1]Quadratic sieveThe classical subexponential factoring bound; practical up to about 100 digits.

L_n[⅓, 1.92]Number field sieveThe best known general algorithm, and the basis of every published RSA record.

u^−uSmoothness densityThe probability that a number near x is y-smooth, with u = ln x / ln y.

829 bitsLargest RSA factoredRSA-250 in 2020, using roughly 2,700 core-years — the empirical anchor for key size guidance.

Executive summary

All modern general-purpose factoring algorithms search for a congruence of squares: x² ≡ y² (mod n) with x ≢ ±y, from which gcd(x−y, n) is a proper factor with probability at least 1/2. The engineering problem is manufacturing such congruences efficiently.

The answer is to collect many relations — numbers that factor completely over a fixed set of small primes — and then find a subset whose product is a perfect square by solving a linear system over F₂ on exponent-parity vectors. The identical structure, with logarithms in place of exponents, computes discrete logarithms; that variant is called index calculus.

Choose a factor base
The primes below a bound B, sized by balancing how rare smooth numbers are against how many relations are needed.
Collect relations by sieving
Evaluate a polynomial over a range and detect B-smooth values by adding log p at arithmetic-progression positions rather than trial dividing.
Build the exponent matrix
One row per relation, one column per factor-base prime, entries the exponents modulo 2 — an extremely sparse binary matrix.
Find a kernel vector
A dependency identifies a subset of relations whose product is a square. Wiedemann or block Lanczos, never dense elimination.
Take a gcd
Form the two square roots and compute gcd(x−y, n). On failure use another kernel vector.

Contents

Smooth numbers: the resource being consumed

Definition D1

y-smooth

An integer is y-smooth if all of its prime factors are at most y. Writing ψ(x,y) for the count of y-smooth numbers up to x, and u = ln x / ln y, the Dickman–de Bruijn estimate gives ψ(x,y)/x ≈ u^−u over the range relevant to these algorithms.

Smoothness probabilities
u = ln x / ln y	≈ u^{−u}	Reading
2	1/4	Half the digits smooth: common
3	1/27	Still frequent
5	1/3,125	Sieving territory
8	≈ 6 × 10⁻⁸	Needs a very large sieving range
12	≈ 10⁻¹³	Only viable with a huge factor base

The optimisation is a trade-off: a larger factor base makes relations more common but requires more of them, and enlarges the linear algebra. Balancing the two is what produces the L[½] and L[⅓] exponents.

Theorem T1

Where L-notation comes from

With a factor base of size B = L_n[½, β], relations are found with probability about L_n[½, −1/(2β)] and about B of them are needed. Total cost is L_n[½, β + 1/(2β)], minimised at β = 1/√2 to give L_n[½, √2] for the plain method — refined to L_n[½, 1] for the quadratic sieve because its candidate values are around √n rather than n.

Contents

Index calculus for discrete logarithms

The same architecture computes logarithms in ℤ*_p. The critical structural feature is that the expensive stages depend only on p, not on the target element.

Relation collection
Compute g^k mod p for random k and keep those results that are B-smooth. Each gives a linear equation in the unknown logarithms of the factor-base primes.
Linear algebra modulo q
Solve the system for log_g p_i for every factor-base prime, working modulo the group order rather than modulo 2.
Individual logarithm (descent)
For a target h, find s with h·g^s smooth, then read off log_g h from the stored table.

Precomputation is amortised across every user of the same prime

The first two stages cost the overwhelming majority of the work and are performed once per prime p. Every subsequent individual logarithm is comparatively cheap. When thousands of deployments share one standardised prime, an adversary who completes the precomputation can break all of them — the observation at the heart of the Logjam analysis, and the reason 1024-bit finite-field Diffie–Hellman is deprecated.

No comparable attack is known for elliptic curve groups, because there is no useful notion of a point being smooth. That single structural difference is why 256-bit curves are considered comparable in strength to 3072-bit prime fields.

Contents

The quadratic sieve

Quadratic sieve, outline

m ← ⌈√n⌉; Q(t) = (t + m)² − n // small values near t = 0
factor base ← { p ≤ B : (n ∣ p) = 1 } // only primes for which n is a QR mod p
for each p in the factor base:
solve t² ≡ n (mod p) to find the two positions where p ∣ Q(t)
add log p to sieve[t] at every position in those arithmetic progressions
collect t with sieve[t] near log|Q(t)| → candidate smooth relations, verified by trial division
build the exponent-parity matrix over F₂; find a kernel vector
x ← ∏(t + m), y ← √(∏ Q(t)); return gcd(x − y, n)

L_n[½, 1]. The sieve replaces trial division by additions in arithmetic progressions — the reason it outperforms earlier congruence-of-squares methods by a wide margin.

Only half the primes qualify. A prime p can divide Q(t) only if n is a quadratic residue modulo p, which halves the factor base for free.
Multiple polynomials (MPQS) switch to a fresh quadratic once Q(t) grows too large, keeping candidate values small throughout and giving a large constant-factor gain. Self-initialising variants amortise the polynomial setup.
Large prime variations keep near-smooth relations with one or two prime factors just above B, then match them into usable relations. This is worth a substantial factor in practice.
The gcd can fail. Roughly half of kernel vectors yield the trivial factorization; extra relations provide several independent attempts from one run.

Contents

The number field sieve and record computations

The number field sieve replaces the rational quadratic with a pair of polynomials, one of which is factored in a ring of algebraic integers. The values that must be smooth are then far smaller relative to n, which is what reduces the exponent from ½ to ⅓.

Cost comparison
Algorithm	Complexity	Crossover	Comment
Trial division	O(√n)	—	Only for tiny inputs or as a pre-filter
Pollard rho	O(n^1/4)	—	Excellent for small factors
Pollard p−1	depends on smoothness of p−1	—	Why RSA primes must be strong
Elliptic curve method	L_p[½, √2] in the factor size	—	The best method for finding medium factors
Quadratic sieve	L_n[½, 1]	up to ≈ 100 digits	Simpler; still competitive in that range
Number field sieve	L_n[⅓, 1.92]	beyond ≈ 110 digits	Every published RSA record

ECM's cost depends on the size of the factor sought rather than the modulus, so it is always run first to strip off any small or medium factors before a sieve is attempted.

Published RSA factoring records
Challenge	Bits	Year	Approximate effort
RSA-512	512	1999	≈ 8,000 MIPS-years
RSA-768	768	2009	≈ 2,000 core-years
RSA-240	795	2019	≈ 900 core-years
RSA-250	829	2020	≈ 2,700 core-years

Effort figures are not directly comparable across eras because hardware and algorithm engineering both improved; they are cited as anchors for extrapolation, which is how key-size recommendations are derived.

What this means for key sizes

Extrapolating the number field sieve from these records puts 1024-bit RSA within reach of a well-resourced adversary and 2048-bit comfortably out of reach with foreseeable classical technology. Current guidance is 3072 bits for long-term confidentiality, or a move to elliptic curves for equivalent strength at far smaller sizes. A cryptographically relevant quantum computer would change the analysis entirely, since Shor's algorithm is polynomial time.

Contents

Engineering the three stages

Where the effort actually goes
Stage	Share of work	Dominant constraint	Parallelism
Polynomial selection (NFS)	small but decisive	Search quality determines the constant factor for everything downstream	Embarrassingly parallel
Sieving	majority of CPU time	Memory bandwidth and cache behaviour	Embarrassingly parallel; distributable to volunteers
Linear algebra	a large minority	Interconnect latency; must run on a tightly coupled cluster	Block methods only; limited scaling
Square root and gcd	negligible	—	Trivial

The linear algebra stage, not sieving, is the practical bottleneck for the largest computations, because it cannot be spread across loosely connected machines.

Relation surplus is deliberate. Collect noticeably more relations than factor-base primes so that the kernel has dimension several, giving multiple independent chances at a non-trivial gcd.
Structured Gaussian elimination first. Removing singleton columns and merging light rows shrinks the matrix substantially before the iterative solver runs.
Filtering and deduplication matter. Distributed sieving produces duplicate relations; deduplication and careful filtering can change the size of the final matrix by a large factor.
Verify the factorization. The final answer is trivially checkable by multiplication, so no probabilistic doubt survives the end of the computation.

Contents

Quick reference and FAQ

Facts
Fact	Statement
Congruence of squares	x² ≡ y², x ≢ ±y ⇒ gcd(x−y,n) is a proper factor
Success per kernel vector	≥ 1/2
Smoothness density	u^−u with u = ln x / ln y
Quadratic sieve	L_n[½, 1]
Number field sieve	L_n[⅓, 1.92]
ECM	L_p[½, √2] in the size of the factor
Index calculus in ℤ*_p	Same shape; precomputation amortises per prime
Largest public RSA factorization	829 bits (RSA-250, 2020)

Why does the linear algebra use F₂ rather than the integers?

Only the parity of each exponent matters, because a product is a perfect square exactly when every exponent is even. Working over F₂ makes a row a bit vector and an elimination step an XOR, which is both smaller and far faster.

Is elliptic curve factoring obsolete now that NFS exists?

No — they solve different problems. ECM's cost scales with the size of the factor being sought, so it efficiently strips small and medium factors; NFS's cost scales with the modulus. Production factoring always runs ECM first.

Do special-form moduli need larger keys?

Yes. The special number field sieve handles numbers of the form r^e ± s with a smaller constant, L_n[⅓, 1.53]. This does not affect ordinary RSA moduli but does affect Mersenne-like numbers and some proposed structured parameters.

Why must RSA primes avoid smooth p − 1?

Pollard's p−1 method finds p quickly when p−1 has only small prime factors, and Williams' p+1 method does the same for p+1. Strong-prime requirements in older standards exist for this reason; with random primes of modern sizes, the risk is negligible, which is why current standards no longer mandate them.

Contents

References and further reading

V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 16.
C. Pomerance, 'A tale of two sieves', Notices of the AMS 43 (1996) 1473–1485.
A. K. Lenstra and H. W. Lenstra Jr. (eds.), The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, Springer, 1993.
F. Boudot et al., 'Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment', CRYPTO 2020, LNCS 12171, 62–91.
H. W. Lenstra Jr., 'Factoring integers with elliptic curves', Annals of Mathematics 126 (1987) 649–673.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: subexponential-factoring-and-index-calculusReview cycle: annual

Subexponential Factoring and Index Calculus

Executive summary

Choose a factor base

Collect relations by sieving

Build the exponent matrix

Find a kernel vector

Take a gcd

Smooth numbers: the resource being consumed

y-smooth

Where L-notation comes from

Index calculus for discrete logarithms

Relation collection

Linear algebra modulo q

Individual logarithm (descent)

The quadratic sieve

The number field sieve and record computations

Engineering the three stages

Quick reference and FAQ

References and further reading

Continue learning

KEVOS Intelligence

Executive summary

Choose a factor base

Collect relations by sieving

Build the exponent matrix

Find a kernel vector

Take a gcd

Smooth numbers: the resource being consumed

y-smooth

Where L-notation comes from

Index calculus for discrete logarithms

Relation collection

Linear algebra modulo q

Individual logarithm (descent)

The quadratic sieve

The number field sieve and record computations

Engineering the three stages

Quick reference and FAQ

Related pages in this library

References and further reading

Continue learning