Interactive
Playground
Run the General Number Field Sieve in your browser. Real Python code, real factorization.
Configuration
Parameters
Small semiprimes work best (91, 143). Max 20 digits in playground - download notebook for larger numbers.
Degree 1 works for small numbers. Higher degrees for larger n.
Primes up to this value form the factor base.
Search range for smooth relations.
Output
Results
Example Numbers
Green numbers work reliably with default parameters.
The Algorithm
Step 1 - Polynomial Selection: Choose m = floor(n^(1/d)) and construct f(x) = x - m. Both f and g share m as a root mod n.
Step 2 - Sieving: Find pairs (a,b) where a - mb factors completely over small primes (B-smooth). These are our relations.
Step 3 - Linear Algebra: Build an exponent matrix over GF(2). Find dependencies where all exponents are even.
Step 4 - Square Root: Combine relations to get x² ≡ y² (mod n). Then gcd(x-y, n) usually gives a factor.