The number field sieve for discrete logarithms takes the factor-base idea of index calculus and lifts it into algebraic number fields.
Instead of collecting relations among small rational primes only, NFS-DL builds two algebraic worlds that map into the same finite field. Smooth principal ideals on both sides yield linear relations among logarithm-like quantities attached to prime ideals. Large sparse linear algebra solves those virtual logarithms. A final descent rewrites one target until every leaf has a known log.
This is Guide 28 in the Bukit Timah Tutor Computational Number Theory series. It follows Guide 27: Index Calculus and parallels the factoring pipeline in Guide 23: Number Field Sieve.
1. The discrete-log target subgroup
Let p be prime and let g generate a subgroup of F_p* of order ℓ, usually a large prime divisor of p−1. Given h in <g>, find
x mod ℓ such that g^x=h.
Working modulo a large prime subgroup order makes the final relation linear algebra occur over the field F_ℓ, avoiding the nonunit-pivot complications of a composite exponent modulus.
If the ambient group order has smooth cofactors, use Pohlig–Hellman first and reserve NFS-DL for the large prime-order component.
2. Why ordinary index calculus eventually runs out of room
Classical index calculus looks for residues that factor over small rational primes.
For very large prime fields, direct smoothness among ordinary residues becomes too rare for the best asymptotic performance. NFS-DL creates algebraic representations whose norms are smaller and whose smoothness can be searched simultaneously on two sides.
The strategy is not to change what a logarithm means. It changes the representation in which relations are found.
3. Polynomial bridges
Choose polynomials f0,f1 with compatible roots modulo p. In a simple prime-field presentation, one side may be linear:
f1(T)=T−m,
while another irreducible polynomial f0 satisfies
f0(m) ≡0 (mod p).
Let α be a root of f0. Substitution α→m gives a map from suitable algebraic expressions in the number field Q(α) into F_p.
More sophisticated NFS-DL variants choose two non-linear polynomials to balance norm sizes.
4. A tiny exact bridge modulo 101
Take p=101 and m=10. Choose
f(T)=T²+T−9.
Then
f(10)=100+10−9=101≡0 (mod101).
The discriminant is37, not a rational square, so f is irreducible over Q. Let α satisfy
α²+α−9=0.
The reduction map sends α to10 in F101.
5. Rational and algebraic values from one pair
For coprime integers a,b, compare
R(a,b)=a+10b
with the algebraic element
A(a,b)=a+bα.
They map to the same finite-field residue because α→10.
For f(T)=T²+T−9, the conjugate roots satisfy α+α’=-1 and αα’=-9, so
Norm(a+bα)=a²−ab−9b².
6. Small relation examples
Take (a,b)=(-3,1):
R=7, Norm(α−3)=3.
Take (a,b)=(-4,1):
R=6=2·3, Norm(α−4)=11.
Take (a,b)=(1,1):
R=11, Norm(1+α)=−9=−3².
These tiny values illustrate the NFS relation objective: one pair produces manageable factorisation data in two linked representations.
7. Norm factorisation becomes prime-ideal factorisation
The integer norm tells which rational primes can occur, but NFS-DL relations live naturally in prime ideals.
If a rational prime r splits in the number field, several prime ideals may lie above r. The principal ideal (a+bα) must be factored into the correct prime ideals, including ramification and residue-degree information.
Therefore a production relation record cannot replace algebraic ideal factorisation with a bare norm factorisation.
8. Factor bases on two sides
Choose finite sets of small prime ideals in each number field. These are the algebraic factor bases.
On a linear rational side, ordinary small primes play the same role.
A relation is accepted when the principal ideals produced by the pair factor completely over the chosen bases, possibly with controlled large-prime variants.
9. Why logarithms of prime ideals are only virtual
A prime ideal is not itself an element of F_p*, so it does not literally have a discrete logarithm.
NFS-DL assigns virtual logarithms to factor-base prime ideals so that principal-ideal relations become linear equations matching the finite-field logarithm after the number-field maps are applied.
The virtual-log definition includes correction data for units and valuations. Its purpose is algebraic bookkeeping: turn multiplicative ideal relations into additive linear relations modulo ℓ.
10. Principal relations become linear equations
Suppose a principal ideal factors as
(a+bα)=p1^e1 ... pr^er.
After mapping into the finite field and including the required unit/special-map corrections, the relation contributes an equation of the form
finite-field log of image(a+bα) ≡ Σ e_i vlog(p_i) + correction terms (mod ℓ).
Collect enough such equations from both sides to solve for the virtual logs.
11. Why unit corrections are necessary
Ideal factorisation forgets multiplication by units:
(uα)=(α)
for every unit u.
But the finite-field images of uα and α can have different discrete logarithms. Therefore ideal valuations alone do not determine the element log.
Practical NFS-DL introduces additional maps that record the missing unit directions.
12. Schirokauer maps
Schirokauer maps provide computable linear data that replaces explicit computation of a full system of fundamental units in large number fields.
They add extra columns to the relation matrix. These columns account for the unit contribution needed to make virtual logarithms well defined modulo the target subgroup order ℓ.
The exact construction depends on the number field and subgroup order and belongs to the technical core of NFS-DL implementations.
13. Relation collection
Search over coprime pairs (a,b). Sieve for divisibility by rational primes and algebraic prime ideals.
As in factoring NFS, modular roots determine lattice progressions where divisibility occurs. Logarithmic sieve scores identify candidates likely to be smooth.
Exact factorisation verifies every surviving candidate before it becomes a relation row.
14. Special-q sieving
Fix a prime ideal q larger than the ordinary factor-base bound and restrict the search to pairs whose algebraic value is divisible by q.
Those pairs form a lattice. A reduced lattice basis produces efficient sieve coordinates.
The known q factor makes the remaining cofactor smaller and more likely to factor over the ordinary base.
15. Large-prime recombination
Relations with one or more controlled prime ideals outside the base can be retained as partial relations.
When compatible partials share large primes, combine them through matching or graph cycles so that the unwanted large-prime contributions cancel.
This greatly increases relation yield but creates a substantial filtering stage.
16. Filtering and matrix construction
Raw relations contain duplicates, singleton prime ideals, dense local structures and partial-relation components.
Filtering removes columns that cannot participate in a final dependency and performs structured elimination while protecting enough information to recover virtual logs.
The resulting matrix is still enormous but sparse.
17. Sparse linear algebra modulo ℓ
The target subgroup order ℓ is usually prime, so the relation matrix is solved over F_ℓ.
Block Wiedemann and related Krylov-space methods are well suited because they require repeated sparse matrix-vector products rather than dense elimination.
The output assigns virtual logarithms to the surviving factor-base prime ideals and correction columns.
18. A logarithm database is not yet an individual answer
After linear algebra, we know virtual logs for many small algebraic objects.
A target h is generally not one of those objects. We still need to express h as a product of elements whose virtual logs are known.
This is the individual logarithm phase.
19. Booting the target
First multiply h by a known power g^t or choose another equivalent representation so that the target lifts to an algebraic element with a relatively smooth norm.
If
h g^t = image(β),
then
log_g(h) ≡ log_g(image(β))−t (mod ℓ).
The boot step aims to make β suitable for further descent.
20. Descent
If β factors into prime ideals larger than the factor base, choose one such special-q prime ideal and generate new relations containing it together with smaller prime ideals.
Solve that relation for the virtual log of q. Repeat recursively.
The descent forms a tree whose root is the target and whose leaves are factor-base prime ideals with known virtual logs.
21. Descent must decrease difficulty
A useful descent relation replaces one hard prime ideal by several easier objects according to norm, degree or a chosen smoothness measure.
If new relations repeatedly introduce equally large or larger primes, the recursion can stall.
Descent algorithms therefore tune special-q bounds, lattice sieves and smoothness parameters by level.
22. Reconstruct the target logarithm
Once every descent leaf has a known virtual logarithm, propagate values upward through the relation tree.
Combine the algebraic-side and correction terms to obtain the finite-field logarithm of the booted target, then subtract the known randomisation exponent t.
Finally verify
g^x ?= h.
23. The tiny bridge is illustrative, not a full NFS-DL computation
In the mod101 example, α→10 and the displayed pairs exactly verify the polynomial-map and norm arithmetic.
They do not constitute a production virtual-log database. A full NFS-DL computation would need explicit prime-ideal factor bases, unit corrections, a relation matrix modulo the chosen subgroup order and a complete descent.
Keeping this distinction clear prevents a simple norm identity from being mistaken for a complete discrete-log algorithm.
24. NFS-DL versus NFS factoring
The two algorithms share polynomial selection, number fields, smoothness, sieving, filtering and sparse linear algebra.
But the linear algebra asks different questions.
Factoring NFS seeks parity dependencies that make products into squares. NFS-DL solves a modular linear system for virtual logarithms.
The final phases also differ: factoring computes algebraic/rational square roots; NFS-DL performs an individual logarithm descent.
25. Precomputation reuse
NFS-DL’s expensive relation collection and linear algebra are tied to the field and target subgroup, not to one h.
Once virtual logs are known, many individual targets can reuse the database and pay primarily for booting and descent.
This precomputation/query split is one of the most important operational features of index-calculus families.
26. Complexity viewpoint
Daniel Gordon’s foundational prime-field NFS-DL algorithm achieved an L_p[1/3,c] subexponential family, improving the exponent scale over older index-calculus methods for large prime fields.
Modern variants, polynomial selections and finite-field extension techniques change constants and regimes, but the L[1/3] number-field-sieve architecture remains the central large-characteristic framework.
As always, asymptotic superiority does not identify the crossover point for a particular implementation.
27. Why this does not transfer directly to generic elliptic curves
NFS-DL exploits finite-field representation: elements lift to algebraic integers and ideals that factor into smaller objects.
A generic elliptic-curve group does not supply an analogous smooth factorisation representation for points.
This is why generic square-root algorithms such as Pollard rho remain central for ordinary elliptic-curve discrete logarithms.
28. Verification receipts
Retain the polynomial pair and common-root map. For every relation, retain (a,b), exact ideal factorisations on both sides and all correction-map values.
Retain the filtered matrix definition and enough information to verify the solved virtual logs against the relation equations.
For an individual logarithm, retain the boot representation and complete descent tree. Every internal relation should re-factor exactly, and the final x should satisfy g^x=h.
29. Common mistakes
1. Treating norm factorisation as identical to prime-ideal factorisation. 2. Calling a prime ideal’s virtual log an ordinary element logarithm. 3. Omitting unit/Schirokauer correction columns. 4. Solving the relation system modulo p instead of the subgroup order ℓ.
5. Confusing factoring-NFS parity dependencies with NFS-DL logarithm equations. 6. Treating precomputation as free. 7. Presenting a one-step smooth target as representative of full large-field descent. 8. Accepting a computed log without final exponentiation verification.
30. Practice set
1. What is the target exponent modulus in a prime-order subgroup? 2. Explain why NFS-DL uses number fields. 3. Verify f(10)=101 for f(T)=T²+T−9. 4. Derive Norm(a+bα)=a²−ab−9b².
5. Compute the rational and norm values for (−3,1). 6. Do the same for (−4,1). 7. Why is norm factorisation insufficient? 8. What is a virtual logarithm?
9. Why do units create missing information? 10. What job do Schirokauer maps perform? 11. What is special-q sieving? 12. Why is filtering required?
13. What does the sparse linear algebra solve? 14. Define the booting phase. 15. Define descent. 16. What is the final verification?
31. Answers
1. The subgroup order ℓ. 2. Algebraic norms and ideals create smaller smooth objects and richer relation structure. 3. 100+10−9=101. 4. Multiply a+bα by its conjugate and use α+α’=-1, αα’=-9.
5. R=7 and norm3. 6. R=6 and norm11. 7. A rational prime may split into several prime ideals with distinct relation roles. 8. A linear bookkeeping value assigned to prime ideals so principal relations correspond to finite-field logs modulo ℓ.
9. Multiplying by a unit leaves the principal ideal unchanged but can change the finite-field element log. 10. They encode unit directions as additional linear correction columns. 11. Sieve in a lattice of pairs known to be divisible by a selected larger prime ideal. 12. Raw relations are too large and contain duplicates, singletons and partial structures.
13. Factor-base virtual logarithms and correction variables modulo ℓ. 14. Find a favourable algebraic representation of the target, usually after multiplying by a known power of g. 15. Recursively express larger prime ideals in terms of smaller ones until reaching the known base. 16. Check g^x=h.
Sources and further study
Daniel M. Gordon, Discrete Logarithms in GF(p) Using the Number Field Sieve, SIAM Journal on Discrete Mathematics 6(1), 1993, 124–138, gives the foundational prime-field NFS-DL framework. Aurore Guillevic, Computing Individual Discrete Logarithms Faster in GF(p^n) with the NFS-DL Algorithm, develops the individual-log booting and descent perspective for extension fields.
Computational Number Theory — Batch 07
Guide 25: Pohlig–Hellman, Subgroup Decomposition and CRT Reconstruction
Guide 26: Pollard Rho for Discrete Logarithms, Collision Equations and Parallel Search
Guide 27: Index Calculus, Factor Bases, Relation Collection and Individual Logarithms
Guide 28: Number Field Sieve for Discrete Logarithms, Virtual Logs and Descent