Introduction
What is GNFS and why does it matter? A high-level overview of integer factorization.
Documentation
Learn GNFS
Work through each stage of the General Number Field Sieve algorithm with interactive examples.
1
Polynomial Selection
How to choose polynomials that share a root modulo n, enabling the sieve to work.
2
Sieving
Finding smooth relations using logarithmic sieving on both algebraic and rational sides.
3
Linear Algebra
Building an exponent matrix and finding its nullspace over GF(2) using Gaussian elimination.
4
Square Root Step
Combining relations to form a congruence of squares and extracting factors via GCD.
Full Pipeline
See all four stages work together to factor an integer from start to finish.