Quadratic Sieve

Purpose: Factor large integers in sub-exponential time $L_n[1/2,1]=\exp ((1+o(1))\sqrt{\ln n\ln \ln n})$ — the fastest known method for numbers of 60-100 digits, and the second fastest overall after the general number field sieve.

The Idea: congruence of squares

If you can find $x,y$ with
$x^2\equiv y^2(\mathrm{mod}n),x\not\equiv \pm y(\mathrm{mod}n),$
then $\gcd (x-y,n)$ is a non-trivial factor, since $n\mid (x-y)(x+y)$ but $n$ divides neither factor. This is Fermat’s old idea; QS is a systematic way to manufacture such a congruence.

Algorithm

1. Pick a factor base $B=\{p_1,\dots ,p_k\}$: the primes up to a bound for which $n$ is a quadratic residue (checked with the Legendre symbol — otherwise $p$ can never divide $Q(x)$).
2. Define $Q(x)=(x+\lceil \sqrt{n}\rceil {)}^2-n$. For small $x$, $Q(x)$ is small, so it is more likely to be $B$-smooth (factor completely over $B$).
3. Sieve. Rather than trial-dividing each $Q(x)$, note that $p\mid Q(x)$ exactly on an arithmetic progression of $x$ (found by solving $Q(x)\equiv 0(\mathrm{mod}p)$ with Tonelli-Shanks). March through an array subtracting $\log p$ at those positions; entries whose accumulated logs match $\log |Q(x)|$ are smooth. This sieving step is the entire speed advantage.
4. Collect $k+1$ smooth relations. Each gives an exponent vector mod 2 over the factor base.
5. Linear algebra. Find a subset whose exponent vectors sum to zero mod 2 — a null-space vector of a $k\times (k+1)$ matrix over ${\mathbb{F}}_2$. With $k+1$ vectors in a $k$-dimensional space, one always exists.
6. That subset’s product is a perfect square on both sides, giving $x^2\equiv y^2$. Compute $\gcd (x-y,n)$; retry with another null-space vector if it is trivial (happens about half the time).

Complexity

• Time: $L_n[1/2,1]$ — sub-exponential but super-polynomial
• The optimal factor base size is about $L_n[1/2,1/2]$ primes
• The linear algebra is done with block Lanczos or Wiedemann over ${\mathbb{F}}_2$, not Gaussian elimination, because the matrix is huge and sparse

Where each method wins

Digits of $n$	Best method
≤ 19 (64-bit)	Pollard’s rho
20 – 60	ECM (especially if a factor is small)
60 – 100	Quadratic Sieve
> 100	General Number Field Sieve, $L_n[1/3,1.92]$

Not a competitive programming tool

No contest asks you to factor a 90-digit number. QS is here for completeness and because the congruence of squares idea — build relations, then do linear algebra over ${\mathbb{F}}_2$ — recurs in problems about XOR bases and subset-parity constructions.

Variants / Use Cases

• Multiple Polynomial QS (MPQS) — use many polynomials $Q(x)$ so the values stay small over a wider range; the standard practical version
• Self-Initialising QS (SIQS) — cheap polynomial switching, the fastest QS variant
• Lenstra ECM — better when a medium factor exists; QS’s cost depends only on $n$, ECM’s on the smallest factor
• Integer Factorization — the topic page
• Wiedemann / block Lanczos — the sparse linear algebra QS depends on