Quadratic sieve

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Quadratic sieve: a simple, practical way to factor integers

What it is
- The quadratic sieve (QS) is an algorithm for factoring integers. It’s one of the fastest general-purpose methods still practical for numbers up to about 100 digits and is simpler to implement than the number field sieve (NFS).

How it works in brief
- QS tries to find a pair of numbers that satisfy a^2 ≡ b^2 (mod n), where n is the number to factor. If a^2 ≡ b^2 (mod n) but a ≠ ±b (mod n), then gcd(a−b, n) or gcd(a+b, n) gives a nontrivial factor of n.
- The work happens in two phases:
1) Data collection (sieving): generate many values y = x^2 mod n and keep those that factor completely over a small set of primes called the factor base. Each such value is a “relation.”
2) Data processing (linear algebra): turn each relation into a vector of prime exponents modulo 2. Find a subset of relations whose exponents add to zero modulo 2 (a linear dependency). This means the product of their y-values is a perfect square modulo n, giving a^2 ≡ b^2 (mod n).

Key ideas to make it work
- Factor base: choose small primes p for which n is a quadratic residue mod p. A y(x) that factors completely over this base is called smooth.
- Parity math: only the even/odd status of prime exponents matters, so we work modulo 2. Finding a subset of relations that sums to zero in this parity space is a linear algebra problem.
- Why smoothness helps: if y(x) factors over the small primes, we can assemble many relations with manageable data sizes. We don’t want y(x) to introduce large prime factors.

The sieve and how relations are used
- The sieve is like a sieve of Eratosthenes: we scan x values and mark those where y = x^2 mod n has factors from the base. When a y is smooth, we record its factorization as a relation.
- After collecting enough relations (more than the number of primes in the base), we solve a system of linear equations (over the field with two elements) to find a dependency.
- This dependency gives a candidate a^2 ≡ b^2 (mod n). Computing gcd(a−b, n) or gcd(a+b, n) then yields a nontrivial factor.

Why this is practical
- The data collection phase can be easily parallelized across many processors.
- The matrix in the linear algebra phase is large and memory-intensive, so it’s more challenging to parallelize efficiently.
- There are optimized variants to speed things up, such as multiple polynomial QS (MPQS) and self-initializing QS (SIQS). These variants use more than one polynomial, help with parallelization, and manage memory better. They also use techniques to find some “large primes” and merge partial relations to form full ones.

A quick, simple example (conceptual)
- For a small number n, QS looks for x values where y = x^2 mod n factors completely over a tiny factor base. When you multiply several such y-values, the product can become a square modulo n. Collecting enough such relations lets you build a square on both sides and then compute a nontrivial factor of n via a gcd calculation.

History and practical notes
- Before the number field sieve (NFS) became dominant, QS was the fastest general-purpose factoring method for many sizes.
- In practice, QS and its variants are used for numbers that are not huge but still hard to factor with simpler methods. Large-scale factoring today often uses NFS, with QS still contributing in certain ranges.
- Notable records include early QS-based factorizations of RSA numbers and later improvements using MPQS/SIQS and large-prime tricks. Modern implementations also emphasize parallelization and careful memory management to handle big data sets.

Bottom line
- The quadratic sieve is a practical, general-purpose factoring method that blends number theory with a clever data-collection and linear-algebra approach. It quickly turns a hard factoring problem into finding a set of relations whose product is a square, then uses a gcd to extract a factor.