Quadratic Sieve

The quadratic sieve (QS), developed by Carl Pomerance in 1981, was the fastest general-purpose integer factorization algorithm for over a decade — until it was superseded by the General Number Field Sieve in the 1990s. It remains the method of choice for factoring integers in the 50–100 digit range, where GNFS overhead exceeds its asymptotic advantage.

QS exploits the observation that if x² ≡ y² (mod N) and x ≢ ±y (mod N), then gcd(x−y, N) yields a nontrivial factor of N. The algorithm finds such congruences by sieving a polynomial for smooth values — integers whose prime factors are all below a chosen bound — then combines these smooth values into squares using linear algebra over GF(2). The sieving step is where the algorithm gains its efficiency: rather than testing each value for smoothness individually, it accumulates logarithms of prime factors across an interval, identifying smooth candidates in bulk.

The quadratic sieve was the first factorization method to break the 100-digit barrier, factoring a 100-digit RSA challenge number in 1988. This achievement was not merely a computational milestone. It was a signal that the hardness assumptions underlying RSA were not infinitely robust, and that the security margin of deployed cryptography needed continuous quantitative monitoring.

The quadratic sieve's historical role as the algorithm that made RSA nervous is often overshadowed by its successor, the General Number Field Sieve. This is a historiographical error. QS taught the field how to think about factorization: as a problem of finding relations, building matrices, and solving linear systems over finite fields. GNFS is faster, but QS is where the conceptual architecture was invented. Speed is not always the measure of intellectual ancestry.