Modern Factoring Methods
Number Field Sieve: Polynomial Selection and Structure
How the number field sieve achieves its complexity, why polynomial selection matters so much, and the role of number field arithmetic.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0676
The number field sieve is the fastest known general factoring algorithm. Its advantage comes from examining much smaller numbers for smoothness, and how small those numbers are is determined entirely by the polynomial chosen.
The idea
Work simultaneously in the integers and in a number field, seeking pairs that are smooth on both sides. Combining such relations produces a congruence of squares as before.
Why the values are smaller
| Method | Size of values tested |
|---|---|
| Quadratic sieve | Around the square root of the target |
| Number field sieve | Around a sub-exponential function far below that |
Polynomial selection
Two polynomials with a common root modulo the target are chosen. One defines the number field; the other is typically linear. The quality of the choice dominates the total running time.
Polynomial selection
- Search a large spaceMany candidate polynomial pairs are generated.
- Score by sizeHow small the values will be over the sieving region.
- Score by root propertiesWhether many small primes divide values often — this substantially raises smoothness.
- Optimise locallyRefine the best candidates by small adjustments.
- SelectThe best-scoring pair.
The algebraic side
Smoothness on the number field side means the corresponding ideal factors over a base of prime ideals. This is where the machinery of this collection enters directly.
- Prime ideals and their norms — see ideal norms.
- Prime decomposition to build the algebraic factor base — see simple decomposition.
- Class group and unit obstructions in the final square root step.
- The square root of an algebraic number, a substantial computation in its own right.
Where it wins
The special variant
For targets of special algebraic form, a polynomial with very small coefficients is available immediately, and the method runs considerably faster. This is why numbers of special form are factored well beyond the general record size.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.5. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.