Introduction to GNFS
What is the General Number Field Sieve?
The General Number Field Sieve (GNFS) is the fastest known algorithm for factoring integers larger than about 100 digits. It was developed in the 1990s and has been used to factor increasingly large RSA challenge numbers, demonstrating the practical limits of cryptographic key sizes.
Unlike simpler factoring methods like trial division or Pollard's rho, GNFS works by finding a “congruence of squares” — two numbers whose squares are congruent modulo n. Once we have x² ≡ y² (mod n) with x ≠ ±y, we can often extract a factor using gcd(x - y, n).
The Four Stages
GNFS accomplishes this through four main stages:
- Polynomial Selection: Choose polynomials that share a common root modulo n
- Sieving: Find pairs (a, b) where both algebraic and rational norms are smooth
- Linear Algebra: Find combinations of relations whose exponents sum to even values
- Square Root: Compute the actual square roots and extract factors via GCD
Why Learn GNFS?
Understanding GNFS provides insight into:
- The mathematical foundations of modern cryptography
- Algebraic number theory and its practical applications
- Why RSA key sizes need to keep increasing
- Beautiful connections between abstract algebra and efficient computation
About This Guide
This educational website lets you explore each stage of GNFS interactively. You'll see the actual Python code alongside explanations, and you can run live demonstrations right in your browser using Pyodide.
The implementation is intentionally minimal and readable — production GNFS implementations have many optimizations that would obscure the core ideas. Our goal is to make the algorithm understandable, not to break RSA records.