Stage 2: Sieving
What is Sieving?
The sieving stage is the computational heart of GNFS. Its goal is to find many pairs (a, b) such that both:
- The algebraic norm: bdf(a/b) is B-smooth (only has prime factors ≤ B)
- The rational norm: a - mb is also B-smooth
These pairs are called relations. Once we have enough relations (more than the number of primes in our factor base), we can proceed to the linear algebra step.
Logarithmic Sieving
Rather than trial-dividing every candidate, we use a clever shortcut:
- Initialize a sieve array with log(|value|) for each candidate
- For each prime p in the factor base, find where p divides the norm
- Subtract log(p) from those positions each time p divides
- After processing all primes, positions with values near zero are likely smooth
This is much faster than trial division because subtraction is cheaper than division, and we only trial-factor the promising candidates.
Two-Sided Sieving
Real GNFS implementations sieve on both the algebraic and rational sides simultaneously. This filters out candidates that are only smooth on one side, dramatically reducing the number of trial factorizations needed.
The Relation Object
Each successful relation stores:
Relation(
a = 11, # First coordinate
b = 7, # Second coordinate (coprime to a)
algebraic_value = 40,# b^d * f(a/b)
rational_value = -23,# a - m*b
algebraic_factors = {2: 3, 5: 1}, # 2³ × 5 = 40
rational_factors = {23: 1} # |-23| = 23
)
Interactive Demo
Interactive sieve visualization will be loaded here. Watch the sieve array update as each prime is processed.