Integer Factorization · Number Theory · Cryptography

The General Number
Field Sieve

An interactive guide to the fastest known algorithm for factoring large integers. Learn the mathematics. Explore the code. Run live demonstrations.

Start Learning Try It Out

The Algorithm

Four Stages

Stage 1

Polynomial Selection

Choose polynomials with shared roots modulo n. The foundation of the algebraic structure.

Stage 2

Sieving

Find smooth relations using logarithmic sieve. The computational heart of GNFS.

Stage 3

Linear Algebra

Find dependencies using Gaussian elimination over GF(2). Sparse matrix techniques at scale.

Stage 4

Square Root

Extract factors via congruence of squares. The algebraic payoff.

Interactive Learning

Learn by Doing

📖

Side-by-Side View

Read explanations alongside the actual Python source code that implements each concept.

⚡

Interactive Demos

Run real Python code in your browser. Experiment with different parameters and see results instantly.

🎯

Step by Step

Follow the algorithm through each stage with worked examples and visualizations.

Real Implementation

Not a toy — a working factorization pipeline

Every stage mirrors the real algorithms behind GNFS. Polynomial selection, logarithmic sieving, sparse matrix algebra, and algebraic square roots — all in readable Python.

from gnfs import gnfs_factor

# Factor a semiprime
n = 8051
factors = gnfs_factor(n)
print(f"{n} = {factors[0]} × {factors[1]}")
# → 8051 = 83 × 97

Try it in the playground →

The General Number Field Sieve