The quadratic sieve factors n by collecting many easy congruences until linear algebra forces two different squares to agree modulo n.
The final factor step is elementary: if X²≡Y² (mod n), then n divides (X−Y)(X+Y). A greatest common divisor can reveal a nontrivial factor. The hard work is manufacturing X and Y so that the congruence is nontrivial.
The quadratic sieve does this by examining values x²−n near zero, looking for values built only from a small factor base, and recording prime exponents modulo two. Once enough smooth relations have been collected, a dependency in a binary matrix makes the product of selected x²−n values a perfect square.
This is Guide 22 in the Bukit Timah Tutor Computational Number Theory series. It deepens the sieve overview in Guide 4 and follows Guide 21 on ECM. Return to the BTT Mathematics Hub for the wider estate.
1. The congruence-of-squares idea
Suppose we find integers X and Y satisfying
X² ≡ Y² (mod n).
Then
n | (X−Y)(X+Y).
If X is not congruent to ±Y modulo n, the two gcds
gcd(X−Y,n), gcd(X+Y,n)
often reveal nontrivial factors.
This is the same algebraic endpoint used by Fermat-style factorisation, Dixon’s random-squares method and the number field sieve.
2. Why x²−n is the natural polynomial
Choose x near √n. Then
Q(x)=x²−n
is much smaller than x² itself. Smaller integers have a better chance of factoring completely over a small set of primes.
Every relation automatically gives
x² ≡ Q(x) (mod n).
If we multiply several such relations and make the right-hand side a square, the left-hand side is already a square.
3. A toy factorisation of 91
Take n=91. The integer √91 is a little below 10, so try x=10:
10²−91 = 9 = 3².
Therefore
10² ≡ 3² (mod91).
The congruence is nontrivial because 10 is not ±3 modulo91. Compute
gcd(10−3,91)=gcd(7,91)=7.
The complementary factor is 13.
This is an unusually lucky one-relation example. A real quadratic sieve normally needs many smooth values before a square product appears.
4. Factor bases
Choose a smoothness bound B. The factor base contains small primes p for which n is a quadratic residue modulo p, together with a sign column when negative Q(x) values are allowed.
Why restrict to such primes? If p divides x²−n, then x²≡n mod p. Therefore n must be a quadratic residue modulo p unless p divides n itself.
The Legendre-symbol test from Guide 5 filters candidate primes efficiently.
5. Smooth relations
A value Q(x) is factor-base smooth when all of its prime factors belong to the chosen base.
For example, if the base contains 2,3 and 5, then
Q(x)=2³·3²·5
is smooth. Record its exponent vector
(3,2,1).
For square construction, only exponent parity matters:
(1,0,1) over F2.
6. Why linear algebra appears
Suppose relations i=1,…,r have parity vectors v_i in F2^m. A subset produces a square product precisely when the sum of its parity vectors is zero.
Thus we need a nonzero binary vector c satisfying
V c = 0 over F2.
The nullspace of the exponent-parity matrix identifies relation subsets in which every prime exponent becomes even.
The hard-looking factorisation problem has become linear algebra over a two-element field.
7. Constructing X and Y from a dependency
Suppose the dependency selects relations indexed by S. Multiply their left sides:
X = product of x_i modulo n.
On the right, add the full prime exponents, divide each total exponent by two and form
Y = product of p_j^(E_j/2) modulo n.
Then
X² ≡ Y² (mod n).
Finally compute gcd(X−Y,n) and gcd(X+Y,n).
8. A dependency can be trivial
A nullspace dependency does not guarantee a factor. It may produce X≡Y or X≡−Y modulo n, giving gcd values 1 and n.
Then choose another dependency. When the nullspace dimension exceeds one, several combinations are available.
A practical implementation collects more relations than the minimum number of factor-base columns to increase the chance of useful dependencies.
9. Sieving replaces repeated trial division
Testing every Q(x) by trial division against every factor-base prime wastes work. The sieve uses modular roots.
If r²≡n mod p, then Q(x)=x²−n is divisible by p whenever
x ≡ r or −r (mod p).
Therefore, for each prime p, mark arithmetic progressions of x-values where p divides Q(x). Repeatedly account for higher powers p²,p³,… where appropriate.
After all primes have contributed their logarithmic weights or exact divisions, positions whose residual value is one—or sufficiently small for a large-prime variant—become relation candidates.
10. Roots modulo factor-base primes
The modular square-root algorithms from Guide 5 provide the two roots of n modulo p for odd factor-base primes.
These roots determine exactly where the sieve should step. For a polynomial Q(x)=(x+s)²−n, shift the roots by −s to obtain the progression positions in the local sieve interval.
The arithmetic of quadratic residues is therefore not background decoration; it drives the sieve address calculation.
11. The sign column
If Q(x) can be negative, include −1 as a formal factor-base element. A negative value contributes parity one in the sign column.
A dependency must make the number of selected negative relations even so that the total product is a positive square.
Alternatively, one can choose a sieve interval where the polynomial is positive, but modern formulations often retain the sign explicitly.
12. Large-prime variants
A relation that is smooth except for one moderately larger prime can still be useful. Store it as a partial relation.
Two partial relations containing the same large prime can be multiplied, making that large-prime exponent even and producing a full relation.
Double-large-prime variants allow two such primes and combine partial relations through graph cycles. This substantially increases relation yield in practical implementations.
13. Multiple polynomial quadratic sieve
The original polynomial x²−n gives values that grow as x moves away from √n. Multiple-polynomial variants use many quadratic polynomials whose values remain smaller over useful intervals.
The algebraic condition is preserved: each polynomial is constructed so that its values correspond to squares modulo n after suitable scaling.
Changing polynomials improves smoothness probability and parallelism without changing the final parity-matrix logic.
14. Why smooth numbers are the scarce resource
The probability that a random integer near size X is B-smooth is governed by the ratio log X/log B and the Dickman–de Bruijn smoothness distribution.
A larger factor base increases smoothness probability but creates a wider matrix and more sieve work. A smaller factor base makes relations rarer.
Parameter selection balances relation collection against linear algebra.
15. Sparse linear algebra over F2
The exponent matrix can contain hundreds of thousands or millions of columns in serious computations, but each relation involves only a small fraction of the factor-base primes.
Therefore the matrix is sparse. Algorithms such as block Lanczos or block Wiedemann exploit sparse matrix-vector multiplication rather than dense Gaussian elimination.
The linear-algebra phase returns dependencies, not factors directly. Each dependency must still be converted into X,Y and tested with gcd.
16. Complexity picture
The quadratic sieve is subexponential and historically became the method of choice for many general integers below the sizes where the general number field sieve dominates.
Its heuristic running time is usually expressed in L-notation as roughly
L_n[1/2,1]
up to convention and lower-order terms.
This asymptotic statement describes a family of increasingly large inputs, not a guarantee about where a particular software implementation switches algorithms.
17. Relation verification
Every stored relation should retain x and the full factorisation of Q(x). Verify
x²−n = signed product of factor-base primes.
For a dependency, recompute the total parity vector and ensure it is zero. Reconstruct Y from the half-exponents rather than merely multiplying rounded square roots.
Then verify X²≡Y² mod n before computing gcds.
18. Common mistakes
1. Including primes for which n is not a quadratic residue. 2. Recording only parity and discarding the full exponents needed to construct Y. 3. Forgetting the sign column. 4. Calling every partially smooth value a full relation.
5. Assuming any nullspace vector yields a nontrivial factor. 6. Using cyclic convolution or unrelated transform ideas where exact parity linear algebra is required. 7. Trial-dividing every candidate instead of exploiting sieve roots. 8. Treating a failed dependency as algorithm failure rather than trying another one.
19. Practice set
1. Derive the congruence-of-squares factor step. 2. Factor 91 from 10²−91=9. 3. Define factor-base smoothness. 4. Why is the Legendre symbol useful when building the base?
5. Convert exponent vector (3,2,1) to parity. 6. What matrix equation identifies a square-producing subset? 7. How is Y reconstructed? 8. Why might a dependency be useless?
9. How does the sieve find multiples of a prime p? 10. What is a partial relation? 11. Why use multiple polynomials? 12. Why is the matrix sparse?
13. What does block Lanczos replace? 14. What must be checked before a relation enters the matrix? 15. Is quadratic sieve a primality test? 16. What later algorithm dominates asymptotically for sufficiently large general integers?
20. Answers
1. X²≡Y² implies n|(X−Y)(X+Y), so gcds can split n when the congruence is nontrivial. 2. gcd(10−3,91)=7. 3. Every prime factor lies in the selected base. 4. p can divide x²−n only when n is a square modulo p, aside from primes dividing n.
5. (1,0,1). 6. Vc=0 over F2. 7. Sum full exponents over selected relations and halve each even total. 8. It may yield X≡±Y mod n.
9. From the two modular roots of n mod p, mark the corresponding arithmetic progressions. 10. A relation smooth except for one or a few controlled larger primes. 11. To keep polynomial values smaller and improve smoothness yield. 12. Each relation contains only a small number of factor-base primes.
13. Dense Gaussian elimination on the huge binary matrix. 14. The exact polynomial identity and complete allowed factorisation. 15. No. 16. The general number field sieve.
Sources and further study
Carl Pomerance, The Quadratic Sieve Factoring Algorithm, EUROCRYPT 1984, is the foundational reference. Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, develops factor bases, sieving, large-prime variants and sparse linear algebra in a modern computational setting.
Continue through Batch 06
Return to Guide 21: ECM. Continue to Guide 23: Number Field Sieve and Guide 24: ECPP and Verifiable Prime Certificates.