Modern Factoring Methods
The Quadratic Sieve: Sieving Stage
The sieving stage: identifying smooth polynomial values in bulk using logarithm accumulation rather than trial division.
Engineering / MathematicsModern Factoring Methods2 min readKV-MATH-0673
Sieving is what makes the quadratic sieve fast. Instead of testing each candidate for smoothness, it marks an entire interval at once, reducing the per-candidate cost to almost nothing.
The polynomial
The sieve
The sieving procedure
- Allocate an arrayOne entry per position in the interval.
- For each factor base primeStart at the positions given by the precomputed square roots.
- Step by the primeEvery prime-th position is divisible.
- Add the logarithmAccumulate an approximate logarithm of the prime at each such position.
- ScanPositions whose accumulated total approaches the logarithm of the value are smoothness candidates.
- VerifyTrial divide only the candidates.
Logarithms are approximate
The large prime variation
Values that are smooth except for one prime slightly above the bound are kept. Two such partial relations sharing that prime combine into one full relation.
| Variation | Effect |
|---|---|
| Single large prime | Substantially more relations for little extra work |
| Double large prime | More again; requires graph-based matching |
| Triple and beyond | Diminishing returns; complex bookkeeping |
Memory and cache
Parallelism
Different intervals and different polynomials sieve independently, so this stage distributes perfectly. The subsequent linear algebra does not.
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.