The number field sieve

The NFS is the reason a 2048-bit RSA key and a 224-bit elliptic curve are said to offer comparable security. Both numbers come from the same place: one problem has a subexponential attack and the other does not, so the parameters diverge and keep diverging.

Problems
Integer factorisation; discrete logarithm in Fp×
Cost
LN[1/3, (64/9)1/3] ≈ LN[1/3, 1.923]
Special-form cost
LN[1/3, (32/9)1/3] ≈ LN[1/3, 1.526] (SNFS)
Records
RSA-250 (829-bit factorisation) and DLP-240 (795-bit prime-field DL), both 2019–2020
Structural hazard
Most of the DL work is per-prime precomputation, reusable across every session using that prime

What subexponential means here

Costs in this area are quoted in the L-notation, which interpolates between polynomial and exponential:

LN[α, c] = exp( (c + o(1)) · (log N)α (log log N)1−α ) α = 0 is polynomial in log N; α = 1 is exponential in log N

The number field sieve runs at α = 1/3, with c = (64/9)1/3 ≈ 1.923 in its general form. That exponent is what makes key sizes for RSA and finite-field Diffie–Hellman grow so much faster than elliptic-curve key sizes, where the best known attack is still at α = 1. The commonly quoted equivalences — 2048-bit RSA near a 224-bit curve, 3072-bit RSA near a 256-bit curve — are this asymptotic evaluated at real sizes, with the constants that record computations have calibrated.

The mechanism

The NFS is index calculus carried out in a number field rather than in the integers. To factor N, choose two irreducible polynomials with a common root modulo N; they define number rings that both map into ℤ/Nℤ. Search for elements that are smooth on both sides at once, and each such element gives a multiplicative relation valid modulo N. Enough relations produce a congruence of squares, and a non-trivial factor follows.

Four phases, with sharply different engineering characters:

  1. Polynomial selection. Search for a pair of polynomials with unusually good smoothness yield. Cheap relative to the rest, and worth a lot — a better pair can shorten sieving by a large constant factor.
  2. Sieving. Collect relations. Embarrassingly parallel, arbitrarily distributable, and the bulk of the raw CPU time.
  3. Linear algebra. Solve the sparse system over the relation matrix, with block Wiedemann or block Lanczos. This phase does not distribute freely — it needs tightly coupled machines with fast interconnect, and it is the practical bottleneck at record sizes.
  4. Square root (factoring) or descent (discrete log). Finish the job: extract the factor, or express the target logarithm in terms of the computed factor-base logarithms.

The discrete-log variant over Fp follows the same structure and the same asymptotic. Where the modulus has a special form — as for Mersenne-like primes, or an RSA modulus built from special primes — the special number field sieve applies instead, at constant 1.526, which is a large advantage at fixed size.

What the records consumed

The state of the art comes from a small number of well-documented computations, and their measured resource use is the honest input to parameter selection.

  • RSA-768 (768-bit factorisation, 2009) by Kleinjung and collaborators: the first public factorisation at that size, and for a decade the reference point for "1024-bit is uncomfortably close".
  • 768-bit prime-field DL (2016) by Kleinjung, Diem, Lenstra, Priplata and Stahlke, establishing that the discrete-log side tracks the factoring side at a modest lag.
  • RSA-240 and DLP-240 (795 bits, 2019) by Boudot, Gaudry, Guillevic, Heninger, Thomé and Zimmermann — run together, deliberately, so the two problems could be compared on the same hardware with the same software. The discrete logarithm cost a few times more than the factorisation of the same size.
  • RSA-250 (829 bits, 2020) by the same team, on the order of a few thousand core-years.

Two things are worth extracting from that history. The factoring and discrete-log costs at equal size are within a small factor of each other, so they should not be given different margins. And progress has come roughly equally from algorithmic refinement and from hardware, which is the argument for treating published records as a moving baseline rather than a fixed one.

The precomputation hazard

For discrete logarithms the cost split matters more than the total. The expensive phases — polynomial selection, sieving, linear algebra — depend only on the prime p, not on the target. Once they are done for a given prime, each individual logarithm modulo that prime costs only a descent, which is comparatively cheap.

Finite-field Diffie–Hellman deployments have historically shared a very small number of fixed primes across enormous numbers of servers. Adrian and collaborators exploited exactly this in the Logjam attack: a one-time precomputation against a standard 512-bit export-grade prime, after which individual connections downgraded to that group could be broken in about a minute. The same paper argued that a state-level precomputation against one of the handful of widely used 1024-bit primes was plausible, and that this would passively expose a large fraction of internet traffic.

There is a related hazard in the other direction. Fried, Gaudry, Heninger and Thomé demonstrated a 1024-bit prime with a hidden special form, for which SNFS applies: a discrete log in that group is within reach of ordinary academic resources, while the prime looks unremarkable to anyone who does not know the trapdoor. Unverifiable Diffie–Hellman parameters are therefore a real risk, not a theoretical one, and the mitigations are named, standardised groups (RFC 7919) or a move to elliptic curves.

The boundary

The NFS needs smoothness — a notion of an element factoring into small pieces. That exists in number rings and in the multiplicative group of a finite field. It does not exist in the group of points on an elliptic curve, which is the entire reason ECC gets away with far smaller parameters; whether a usable substitute can be manufactured is the open question that summation polynomials address.

For a review, the practical consequences are narrow and checkable:

  • RSA and finite-field Diffie–Hellman below 2048 bits should be treated as legacy; 3072 bits is the level commonly matched to a 256-bit curve.
  • Diffie–Hellman groups should be named and verifiable, never an unexplained prime supplied by a peer or a vendor.
  • Downgrade paths to small or export-grade groups are the live exposure, not the primary parameter choice — Logjam was a downgrade attack that the NFS merely made worth mounting.
  • Any prime with an unexplained special structure should be assumed to invite SNFS at 1.526 rather than GNFS at 1.923.

Finally, the NFS is the part of the landscape that Shor's algorithm removes outright: factoring and finite-field discrete logs both fall to polynomial-time quantum algorithms, along with the elliptic-curve problem. Subexponential versus exponential is the classical distinction, and it does not survive into the quantum setting — which is why post-quantum migration replaces all of them at once rather than resizing any of them.

Primary sources

  1. A. K. Lenstra and H. W. Lenstra, Jr. (eds.), "The development of the number field sieve", Lecture Notes in Mathematics 1554 (1993)
  2. T. Kleinjung et al., "Factorization of a 768-bit RSA modulus", CRYPTO 2010
  3. F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann, "Comparing the difficulty of factorization and discrete logarithm: a 240-digit experiment", CRYPTO 2020
  4. D. Adrian et al., "Imperfect forward secrecy: how Diffie-Hellman fails in practice" (Logjam), CCS 2015
  5. J. Fried, P. Gaudry, N. Heninger and E. Thomé, "A kilobit hidden SNFS discrete logarithm computation", EUROCRYPT 2017
  6. D. Gillmor, "Negotiated finite field Diffie-Hellman ephemeral parameters for TLS", RFC 7919