Number Field Sieve
The number field sieve is the fastest known classical factoring algorithm; it constructs square congruences via algebraic number fields with subexponential complexity.
Purpose
To factor large integers (>100 digits) the fastest way, defining the RSA security boundary.
Mechanism
Choose a polynomial f and integer m with f(m)≡0 (mod n), then find smooth elements in the algebraic number field Q(α). Linear algebra combines them so the norms become squares, producing x^2≡y^2 (mod n). Complexity L_n[1/3, (64/9)^(1/3)].
Use cases
- RSA security analysis
- Large-integer factoring
- Cryptography