The fastest method for numbers up to about a hundred digits
The quadratic sieve evaluates Q(x) = (x + ⌈√n⌉)2 − n over an interval. A prime p divides Q(x) exactly at an arithmetic progression of positions, so the whole interval can be processed by adding log p at those positions — no division at all. The multiple polynomial variation keeps values small by switching polynomials, and large prime variations recover near-misses.
Learning objectives
- Explain how sieving replaces trial division for smoothness detection.
- Describe why multiple polynomials are needed.
- Apply single and double large prime variations.
- Choose parameters for a given input size.
- Select an appropriate algorithm for the linear algebra stage.
Section 01Sieving
The key observation: p divides Q(x) exactly when x lies in one of two residue classes modulo p, found once by solving a quadratic congruence with Tonelli–Shanks.
- Choose a factor base of primes p ≤ B with (n/p) = 1.
- For each p, compute the two roots of Q(x) ≡ 0 (mod p) once.
- Allocate an array over the sieving interval, initialised to zero.
- For each p and each root r, add log p to array positions r, r + p, r + 2p, … Additions only — no divisions anywhere.
- Positions whose accumulated total is close to log|Q(x)| are smooth candidates.
- Trial divide only those candidates to obtain exact exponent vectors.
CFRAC trial divides every candidate by the entire factor base and discards nearly all of them. Sieving identifies the smooth ones almost for free and trial divides only those. The asymptotic complexity improves from L[1/2, √2] to L[1/2, 1] as a direct result.
Section 02Multiple polynomials
Values of Q grow linearly with distance from the centre of the interval, so a long interval yields large values that are unlikely to be smooth. MPQS switches to a new polynomial once the values grow too large.
Each polynomial is sieved over a short interval where its values stay small, then a new one is generated. Self-initialising MPQS goes further: choosing a as a product of several factor base primes allows many values of b to be derived cheaply from one a, amortising the setup cost across a whole family of polynomials.
Section 03Large prime variations
| Variation | Accepts | Effect |
|---|---|---|
| Single large prime | One prime factor above B but below a cutoff | Two relations sharing the same large prime combine into one usable relation |
| Double large prime | Two such primes | Combination becomes a graph problem — cycles among relations yield usable relations; substantially more productive |
| Triple large prime | Three | Used in the number field sieve; the cycle-finding becomes the dominant bookkeeping task |
Values that factor completely except for one moderately large prime are far more common than fully smooth values. Exploiting them can improve the relation yield by a large factor, which is why every serious implementation includes at least the single large prime variation.
Section 04Linear algebra
The relation matrix is large and extremely sparse. Ordinary Gaussian elimination causes fill-in and exhausts memory, so sparse iterative methods are used.
Block Lanczos
The standard choice for factoring. Preserves sparsity and works over GF(2) with word-level parallelism.
Block Wiedemann
Distributes better across machines, since the expensive phase can be split. Preferred for the largest computations.
Structured Gaussian elimination
A preprocessing pass that removes singleton columns and merges rows, shrinking the matrix considerably before the iterative solver runs.
Sieving is embarrassingly parallel; the matrix step is not. For record computations the matrix stage often becomes the bottleneck, and parameter choices are made partly to keep the matrix manageable rather than to minimise sieving time alone.
ReferenceFrequently asked questions
How is the factor base bound chosen?
By balancing two costs: a larger base makes relations easier to find but requires more of them and enlarges the matrix. The optimum follows from the L-notation analysis and is refined empirically; implementations ship tables of tested parameters by digit level.
When does NFS overtake the quadratic sieve?
Around 100 to 120 digits, though the crossover depends on implementation quality and available hardware. Below it MPQS is simpler and faster; above it the number field sieve's better exponent dominates decisively.
Why sieve with logarithms rather than exact values?
Because adding a small approximate logarithm is one cheap operation, while dividing is not. Approximation is acceptable since the array is only used to identify candidates, and every candidate is confirmed by exact trial division afterwards.
NavigateContinue in this stream
Curated next steps from this page. The site also surfaces algorithmically related reading below.
ProvenanceSources and further reading
This page is an original KEVOS explanatory article. It presents the underlying mathematics — definitions, algorithms, complexity results and selection criteria — in KEVOS editorial voice. No text is reproduced from any copyrighted source. Where numerical tables are relevant, KEVOS links to live authoritative databases rather than republishing static values.