Engineering / Mathematics — Discrete Logarithms and Factoring
The Quadratic Sieve Algorithm
The quadratic sieve: candidate generation near the square root, sieving for smoothness, and its practical range.
Executive summary
The quadratic sieve generates candidates as values of a quadratic polynomial near the square root of n, so their residues are small and therefore more likely to be smooth.
Sieving detects smoothness across an interval at amortised low cost, which is the algorithmic advance that makes the method practical.
Learning objectives
- State the candidate polynomial and why it is chosen.
- Explain the sieving procedure.
- State the algorithm's practical range.
01Candidate generation
Take Q(x) = (x + ⌈√n⌉)² − n. For x small, Q(x) is small relative to n — of order √n — and is automatically congruent to a square modulo n.
Q(x) = (x + ⌈√n⌉)² − n ≡ (x + ⌈√n⌉)² (mod n)Smallness is the whole point: smaller values are far more likely to be smooth, and the density estimate is highly sensitive to size. Generating candidates near the square root rather than at random is what makes the method work.
02Sieving
Testing each candidate for smoothness by trial division would be far too slow. Sieving inverts the loop: for each factor base prime, mark all the candidates it divides.
Quadratic sieve, sieving phase
modulus n, factor base, sieve intervalsmooth values of Q with their factorisations- Allocate an array of approximate logarithms over the sieve interval, initialised to zero.
- For each factor base prime p:
- Solve Q(x) ≡ 0 (mod p) for the two roots modulo p.
- For each root, step through the interval adding log p at every position divisible by p.
- Report positions whose accumulated total is close to log|Q(x)| as smooth candidates.
- Verify each reported candidate by trial division over the factor base.
amortised O(log log y) per candidateWorking with approximate logarithms rather than exact division is the practical trick: additions replace divisions, and single-byte precision suffices because a verification pass catches the few false positives.
03Practical range and variants
| Variant | Improvement | Effect |
|---|---|---|
| Basic quadratic sieve | — | Baseline |
| Multiple polynomial QS | Many polynomials, short intervals each | Keeps values small throughout; large gain |
| Large prime variation | Allows one prime above the bound | Partial relations combine; more relations per unit work |
| Double large prime | Allows two | Further gains at the cost of more bookkeeping |
The multiple polynomial variant is the important one. A single polynomial produces values that grow as x moves away from zero, so the smoothness rate degrades along the interval. Switching polynomials frequently keeps every candidate small.
- Quadratic sieve
L(1/2, 1)Best method up to roughly 100 digits - Number field sieve
L(1/3, 1.92)Better beyond; all records use it
The quadratic sieve remains the method of choice for moduli in the range where the number field sieve's much larger setup overhead is not yet amortised — roughly up to a hundred digits, which is well below cryptographic sizes but covers many practical factorisation tasks.
04Frequently asked questions
Why does Q(x) ≡ 0 (mod p) have exactly two roots?
Because it is a quadratic congruence modulo a prime, and n must be a quadratic residue modulo p for roots to exist at all. The factor base is restricted to primes for which that holds, which halves its size for free.
Why are approximate logarithms adequate?
Because the test only needs to identify candidates whose accumulated log total is near the expected value. Small errors produce a few false positives, which the verification pass removes cheaply.
When is the number field sieve preferable?
Above roughly 100 to 120 digits. Below that its substantial setup cost — particularly polynomial selection — outweighs its better asymptotic behaviour.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 354-356.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.