B-smooth
An integer is B-smooth if all of its prime factors are less than or equal to B. Finding smooth numbers is the core task of the sieving step.
Reference
Glossary
Key terms and concepts used in the General Number Field Sieve algorithm.
Factor Base
The set of small primes (up to the smoothness bound B) used in sieving. Relations must factor completely over this set.
Relation
A pair (a, b) with gcd(a, b) = 1 such that both the algebraic norm and rational norm are B-smooth. Each relation provides one equation in the linear algebra step.
Algebraic Norm
For a relation (a, b), the algebraic norm is b^d * f(a/b) where f is the algebraic polynomial of degree d. This value lives in the algebraic number field.
Rational Norm
For a relation (a, b), the rational norm is a - mb where m is the common root of the polynomials modulo n. This value is an ordinary integer.
GF(2)
The finite field with two elements (0 and 1) where addition is XOR. Linear algebra over GF(2) finds combinations of relations with even total exponents.
Nullspace
The set of vectors v such that Av = 0. In GNFS, nullspace vectors tell us which relations to combine to get a perfect square.
Congruence of Squares
An equation x² ≡ y² (mod n) where x ≢ ±y (mod n). Such a congruence often reveals a factor: gcd(x - y, n) is usually non-trivial.
Polynomial Selection
The first stage of GNFS: choosing polynomials f(x) and g(x) with a common root m modulo n. Good polynomial selection dramatically affects sieving efficiency.
Logarithmic Sieve
An optimization where we work with logarithms of values. Instead of dividing by primes, we subtract log(p). Positions with small residual logs are likely smooth.
Gaussian Elimination
A systematic method for solving linear systems by transforming the matrix to row echelon form. In GNFS, we use this over GF(2) to find dependencies.
Semiprime
An integer that is the product of exactly two prime numbers. RSA moduli are semiprimes, making GNFS directly applicable to RSA cryptanalysis.