Stage 1: Polynomial Selection

The Key Insight

GNFS works by operating in two different “worlds” simultaneously: the integers and an algebraic number field. The polynomial selection step creates the bridge between these worlds by choosing a polynomial f(x) such that:

• f(x) has a root m modulo n (meaning f(m) ≡ 0 mod n)
• f(x) is irreducible over the rationals
• The coefficients of f(x) are reasonably small

The Construction

This implementation uses the classic (x + m)^d - n construction:

1. Choose the desired degree d
2. Compute m = round(n^1/d), the closest integer to the d-th root of n
3. Expand (x + m)^d and subtract n from the constant term

This ensures that f(-m) = (-m + m)^d - n = -n ≡ 0 (mod n), so m is indeed a root of f(x) modulo n.

Example: n = 8051, degree = 2

The Code

The polynomial selection is implemented in gnfs/polynomial/selection.py. The key function is select_polynomial(n, degree) which returns aPolynomialSelection containing both the algebraic and rational polynomials.