The number field sieve improves the congruence-of-squares strategy by making two different notions of smoothness work together.
On the rational side, we factor ordinary integers. On the algebraic side, we factor norms or ideals in a number field. A carefully chosen polynomial links both sides through a common residue modulo n. After collecting enough simultaneous smooth relations, linear algebra forces square structure on both sides. The square-root phase then maps those structures back to a congruence of squares modulo n.
This is Guide 23 in the Bukit Timah Tutor Computational Number Theory series. It deepens the overview in Guide 4 and follows the quadratic-sieve guide. Return to the BTT Mathematics Hub for the wider Mathematics estate.
1. The same final goal as the quadratic sieve
The general number field sieve (GNFS) still wants
X² ≡ Y² (mod n)
with X not congruent to ±Y modulo n. The final gcd extraction is unchanged:
gcd(X−Y,n), gcd(X+Y,n).
The improvement lies in relation collection. Instead of asking one polynomial x²−n to produce smooth values, NFS engineers two related expressions whose sizes can be substantially smaller in the asymptotic regime.
2. Polynomial selection creates the bridge
Choose an irreducible integer polynomial f of degree d and an integer m such that
f(m) ≡ 0 (mod n).
Let α be a root of f in the number field K=Q(α). Substitution α→m defines a homomorphism from suitable algebraic expressions to Z/nZ because the defining relation f(α)=0 maps to f(m)=0 modulo n.
This is the fundamental bridge between algebraic and rational arithmetic.
3. A tiny polynomial-selection example
For the toy composite n=91, choose m=10 and
f(T)=T²+T−19.
Then
f(10)=100+10−19=91≡0 (mod91).
The discriminant is 77, not a square in Q, so f is irreducible over Q. Let α satisfy α²+α−19=0.
The map α→10 modulo91 sends every polynomial expression in α to a rational residue modulo91.
4. Relation pairs (a,b)
For coprime integers a,b, consider the rational quantity
R(a,b)=a+bm
and the algebraic element
A(a,b)=a+bα.
Under α→m, they map to the same residue modulo n.
For the toy quadratic polynomial above, the algebraic norm is
N(a+bα)=a²−ab−19b²
because α+α’=-1 and αα’=-19.
5. Dual smoothness
A useful NFS relation requires the rational value R(a,b) to factor over a rational factor base and the algebraic ideal generated by a+bα—or, in simplified descriptions, its norm—to factor over a selected algebraic factor base.
For example, with (a,b)=(1,1):
R=11, N(1+α)=1−1−19=−19.
Both sides are extremely smooth in this toy example.
Real GNFS parameters are chosen so that enough pairs have simultaneous smoothness on both sides.
6. Why norms are not the whole algebraic story
If the norm factors as ordinary primes, the corresponding algebraic principal ideal factors into prime ideals above those rational primes. Splitting behaviour matters.
Therefore production NFS relation records include algebraic prime-ideal information, not only an integer factorisation of the norm. Ramified primes, residue degrees, roots of f modulo p and projective prime ideals all affect the factor-base representation.
The number-field machinery from Guide 16 is now computational infrastructure.
7. Rational factor bases
The rational factor base contains small primes used to factor a+bm. Large-prime variants also allow one or more controlled primes beyond the base, later recombined through matching or graph cycles.
As in the quadratic sieve, smoothness bounds trade matrix size against relation yield.
8. Algebraic factor bases
For a small rational prime p, roots r of
f(r) ≡ 0 (mod p)
describe degree-one prime ideals such as (p,α−r) under appropriate order and ramification conditions.
A pair (a,b) is divisible by that algebraic prime ideal when
a+br ≡ 0 (mod p).
This produces sieve progressions analogous to the modular roots used by the quadratic sieve.
9. Sieving in two dimensions
GNFS searches a region of coprime pairs (a,b). For each factor-base prime or prime ideal, modular conditions identify lattice lines or arithmetic progressions where divisibility occurs.
Sieve arrays accumulate approximate logarithms of the expected factors. Candidates whose accumulated score is close to the logarithm of the full rational/algebraic value are trial-divided or exactly factored.
The lattice sieve and special-q variants organise this two-dimensional search more efficiently than naïve enumeration.
10. Special-q sieving
A common modern strategy fixes a relatively large algebraic or rational prime ideal q and restricts the search to pairs whose corresponding value is divisible by q.
The eligible (a,b) pairs form a two-dimensional lattice. Reduce a basis of that lattice and sieve the remaining factor-base contributions inside it.
The factor q is already known to divide one side, which raises the probability that the residual cofactor is smooth.
11. Polynomial selection is an optimisation problem
Any f,m with f(m)=0 modulo n gives the algebraic bridge, but some choices are dramatically better than others.
Good polynomials keep rational and algebraic values small, have favourable root properties modulo small primes and balance the two smoothness probabilities.
Modern GNFS polynomial selection uses search, scoring and rotation techniques. It is not enough to minimise coefficient size alone.
12. Murphy-style root properties
Some polynomials have more roots modulo small prime powers than a random polynomial. That increases the frequency with which algebraic norms gain small prime factors.
Polynomial scoring therefore includes both size and root effects. A slightly larger polynomial can outperform a smaller one if its modular root behaviour substantially improves smoothness yield.
This is a statistical optimisation over relation probability, not a change in correctness.
13. Relation filtering
Raw sieving can produce far more partial and duplicate relations than the final matrix should contain.
Filtering removes duplicates, combines large-prime partials, discards singleton columns that cannot participate in dependencies and performs structured elimination to reduce matrix size while preserving the nullspace information needed later.
A smaller matrix can save enormous linear-algebra time.
14. Characters and sign information
The algebraic product must become a square in the number field, not merely have even prime-ideal valuations.
Additional quadratic-character or Schirokauer-map columns record unit and square-class information that prime-ideal parity alone may miss.
This is one reason NFS linear algebra is conceptually richer than the quadratic-sieve parity matrix.
15. Sparse linear algebra
After filtering, each relation becomes a sparse binary row or column encoding rational prime parity, algebraic prime-ideal parity and additional character information.
Block Lanczos or block Wiedemann methods find dependencies using sparse matrix-vector multiplication over F2.
The matrix phase is often distributed because it requires substantial memory and repeated large sparse operations.
16. What a dependency means
A dependency selects relations whose rational factor exponents are all even and whose algebraic ideal/character data indicate a square-compatible product.
On the rational side, construct an integer square root directly from half-exponents.
On the algebraic side, the product of selected elements is expected to correspond to a square in the number field after the relation and character conditions are satisfied.
17. The square-root phase is a separate algorithm
Recovering the algebraic square root is significantly more difficult than taking half of factor-base exponents.
Methods use ideal arithmetic, algebraic factorisation data, units and modular techniques to construct an algebraic element β satisfying
β² = product of selected algebraic relation elements
up to the exact conventions used by the implementation.
Jean-Marc Couveignes’ contribution in The Development of the Number Field Sieve treats this stage explicitly.
18. Mapping the algebraic square root back modulo n
Apply the homomorphism α→m to β. The algebraic square maps to a rational square modulo n.
The rational-side selected product already supplies another square with the same residue because every individual relation maps a+bα to a+bm.
Thus the two square roots produce
X² ≡ Y² (mod n).
Compute gcd(X−Y,n). Some dependencies are trivial; try another if necessary.
19. Why the number field sieve is faster asymptotically
The general number field sieve has heuristic running time commonly written
L_n[1/3,(64/9)^(1/3)].
The exponent 1/3 improves on the quadratic sieve’s 1/2-scale subexponential behaviour.
This advantage comes from choosing the degree and polynomial so that relation values are much smaller relative to n while smoothness is searched on two linked sides.
20. Special NFS versus general NFS
Numbers with special algebraic form can admit exceptionally good low-coefficient polynomials. The special number field sieve exploits that structure and is faster than GNFS for those inputs.
GNFS works for arbitrary large composite integers through more elaborate polynomial selection.
The foundational NFS work developed first around special-form integers before the general variant became the standard asymptotic method for large general composites.
21. NFS is a pipeline, not one trick
A complete computation contains distinct stages:
polynomial selection → factor-base construction → sieving / relation collection → filtering → sparse linear algebra → square root → gcd factor extraction.
Each stage has different computational bottlenecks and verification receipts.
Optimising one stage can shift the dominant cost to another.
22. Verification receipts
For polynomial selection, retain f,m and verify f(m)≡0 mod n. For each relation, retain (a,b) and the exact rational and algebraic factorisations.
For the matrix dependency, verify every parity and character column sums to zero. For the square-root phase, verify the algebraic square identity or its certified equivalent and the final mapped congruence.
For the final divisor, verify exact divisibility independently.
23. Common mistakes
1. Choosing f without verifying f(m)=0 mod n. 2. Treating algebraic norm factorisation as a complete prime-ideal factorisation. 3. Ignoring units/characters in the square condition. 4. Calling every pair with one smooth side a relation.
5. Skipping filtering and feeding raw partial relations directly into the final matrix. 6. Assuming the algebraic square root is obtained by simply halving ordinary prime exponents. 7. Mixing special-NFS and general-NFS complexity claims. 8. Treating a linear dependency that yields a trivial square congruence as a correctness failure.
24. Practice set
1. State the final congruence NFS wants. 2. Verify f(10)=91 for f(T)=T²+T−19. 3. Explain why α→10 defines the modular bridge. 4. Compute the norm of a+bα for this quadratic field.
5. For (a,b)=(1,1), compute the rational value and algebraic norm. 6. What is dual smoothness? 7. Why are roots of f modulo p useful in sieving? 8. What is special-q sieving?
9. Why is polynomial selection more than minimising coefficients? 10. What does filtering remove? 11. Why are extra character columns needed? 12. What does sparse linear algebra output?
13. Why is the algebraic square-root phase difficult? 14. How does β map back to Z/nZ? 15. State the standard GNFS L-notation scale. 16. Name the seven major pipeline stages.
25. Answers
1. X²≡Y² mod n with X not congruent to ±Y. 2. 100+10−19=91. 3. The defining relation f(α)=0 maps to f(10)=0 modulo91. 4. a²−ab−19b².
5. 11 and −19. 6. Smooth factorisation on both rational and algebraic sides for the same pair. 7. They identify residue classes or lattice lines where the algebraic value is divisible by the corresponding prime ideal. 8. Restrict the search to a lattice of pairs already divisible by a chosen larger prime ideal.
9. Root properties and side balance affect smoothness probability. 10. Duplicates, unusable singletons and partial-relation overhead while preserving dependency information. 11. Even prime-ideal valuations do not alone certify that the algebraic product is a square element. 12. Binary relation dependencies.
13. A square ideal does not immediately hand us a square algebraic generator; units and exact number-field arithmetic intervene. 14. Substitute α→m modulo n. 15. L_n[1/3,(64/9)^(1/3)]. 16. Polynomial selection, factor bases, sieving, filtering, linear algebra, square root, gcd extraction.
Sources and further study
Arjen K. Lenstra, Hendrik W. Lenstra Jr., Mark S. Manasse and John M. Pollard, The Number Field Sieve, STOC 1990, gives the early algorithmic framework. The edited volume The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, collects the foundational papers on sieving, generalisation and square-root computation.
Continue through Batch 06
Return to Guide 22: Quadratic Sieve. Continue to Guide 24: Elliptic Curve Primality Proving and Verifiable Prime Certificates.