The Complete GNFS Pipeline
Putting It All Together
Now that you understand each stage, let's see how they work together to factor an integer. The gnfs_factor function orchestrates the entire pipeline:
Pipeline Overview
Polynomial Selection
select_polynomial(n, degree) → PolynomialSelection
Sieving
find_relations(selection, primes, interval) → [Relation, ...]
Linear Algebra
solve_matrix(relations, primes) → [[indices], ...]
Square Root
find_factors(n, relations, primes) → [p, q]
Parameters
The pipeline accepts several parameters that affect performance:
- degree: Polynomial degree (typically 1 for small n, higher for larger n)
- bound: Smoothness bound B (primes up to B form the factor base)
- interval: Sieve interval radius (how far to search for relations)
- max_rounds: How many times to expand the interval if relations are sparse
Automatic Interval Expansion
The implementation automatically expands the sieving interval if not enough relations are found. It needs at least len(primes) + 1 relations to guarantee the matrix has a non-trivial nullspace.
Example Run
# Factor 8051 using GNFS
from gnfs import gnfs_factor
factors = gnfs_factor(8051, bound=30, interval=50, degree=2)
print(factors) # [97, 83]
# Verify
print(97 * 83) # 8051 ✓
Interactive Demo
Run the complete GNFS pipeline on any integer. Watch each stage execute and see detailed output at every step.