Modern Factoring Methods
Quadratic Sieve Factor Base Selection
Choosing the factor base for the quadratic sieve, the quadratic residue criterion, and the multiplier.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0672
The quadratic sieve looks for smooth values of a quadratic polynomial. Only primes that can divide such values belong in the factor base, and that criterion halves it immediately.
The residue criterion
A prime divides a value of the polynomial only if the target is a quadratic residue modulo that prime. Primes failing this test can never appear and are excluded.
Building the base
Building the quadratic sieve factor base
- Choose a boundBy the smoothness optimisation — see smoothness.
- Enumerate primesUp to that bound.
- Test the Legendre symbolKeep only those where the target is a residue — see symbol computation.
- Compute square rootsFor each retained prime, the two square roots of the target modulo it — see Shanks-Tonelli.
- StoreThe primes with their roots; the roots give the sieve starting positions.
The multiplier
Multiplying the target by a small squarefree integer changes which primes qualify. A well-chosen multiplier admits more small primes into the base, raising the smoothness rate.
Prime powers
Higher powers of factor base primes divide values occasionally. They are handled during sieving by additional passes, or approximated by accepting slightly imprecise logarithm accumulation and catching the difference at the verification step.
Size
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 10.4.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.