The Quadratic Sieve

Every positive integer can be written as a product of primes, and finding that product is called integer factoring. It sounds elementary — yet no one knows a fast general algorithm, and the hardest instances safeguard modern encryption.

For most of history the best strategy was trial division: divide by 2, then 3, then 5, and so on. That works for small numbers, but for a 100-digit number it would take longer than the age of the universe.

In 1981, Carl Pomerance invented the Quadratic Sieve (QS) — an algorithm that runs in sub-exponential time, far faster than trial division, yet (so far as anyone knows) still not polynomial. It held the world speed record for factoring large integers through the 1980s and into the 1990s, and it still reigns for numbers up to roughly 100 digits.

The key insight is elegant: instead of dividing, hunt for pairs of numbers whose squares are congruent modulo $N$ — and build a system of equations over $\mathbb{F}_2$ that, when solved, hands you a factor almost for free. See how factoring relates to public-key cryptography, and how P vs NP looms in the background.

The demo sieves values $x$ near $\lfloor\sqrt{N}\rfloor$, tests whether $x^2 \bmod N$ factors completely over a small factor base of primes, and records each successful factorization as a row in a binary matrix. When enough smooth relations are found it runs Gaussian elimination over $\mathbb{F}_2$ to find a dependency — and that dependency yields a non-trivial factor of $N$.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>N = <select id="nsel">
    <option value="77">77 {{eq_unknown}}</option>
    <option value="143">143 {{eq_unknown}}</option>
    <option value="323" selected>323 {{eq_unknown}}</option>
    <option value="667">667 {{eq_unknown}}</option>
    <option value="1147">1147 {{eq_unknown}}</option>
  </select></label>
  <button id="sieve" type="button">{{btn_run_sieve}}</button>
  <button id="solve" type="button" disabled>{{btn_solve_matrix}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="fb-row" class="fb-row"></div>
<div id="matrix-wrap" class="matrix-wrap"></div>
<div class="status" id="status">{{status_initial}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; align-items: center; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .9rem; }
select { font-size: .9rem; padding: .2rem .4rem; border-radius: 6px; border: 1px solid #adb1b8; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.fb-row { font-size: .8rem; color: #555; margin-bottom: .4rem; min-height: 1.2em; }
.matrix-wrap { overflow-x: auto; margin-bottom: .5rem; }
table { border-collapse: collapse; font-size: .82rem; font-family: ui-monospace, monospace; }
th { background: #1d3557; color: #fff; padding: 3px 7px; text-align: center; white-space: nowrap; }
td { padding: 3px 7px; text-align: center; border-bottom: 1px solid #e0e4e8; }
tr:nth-child(even) td { background: #f5f7f9; }
td.one { color: #e63946; font-weight: 700; }
td.dep { background: #fff3cd !important; }
.status { font-size: .95rem; font-weight: 600; margin-top: .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.status.info { color: #1d3557; }

// Code not found

Notice: collecting smooth relations is the sieve (fast), while solving the matrix is linear algebra (also fast). The bottleneck is finding enough smooth numbers — and the sub-exponential magic is that smooth numbers appear far more often than you might expect, thanks to the structure of $x^2 \bmod N$.

The Quadratic Sieve is not just "better than trial division" — its complexity falls into a mathematically precise middle ground.

• Trial division needs $O(\sqrt{N})$ steps — exponential in the number of digits.
• The Quadratic Sieve runs in $L_N\!\left[\tfrac{1}{2},\,1\right] = e^{(1+o(1))\sqrt{\ln N \ln \ln N}}$ steps — sub-exponential: faster than any pure exponential, slower than any polynomial.
• The General Number Field Sieve (GNFS), invented in 1993, improved the exponent to $L_N\!\left[\tfrac{1}{3},\,1.923\right]$ and dethroned QS for large numbers. QS still wins below roughly $10^{100}$.
• Status: open. No polynomial-time classical algorithm for factoring is known. If one existed, it would break RSA and imply $\text{P} = \text{NP}$ is at least consistent — though factoring is not known to be NP-complete. Shor's algorithm (1994) factors in polynomial time on a quantum computer, but no machine large enough to threaten real keys exists yet.

The practical punchline: RSA-768 (232 digits) fell in 2009 after two years of distributed computation using the GNFS — the same family of ideas that the Quadratic Sieve pioneered.

The Quadratic Sieve is not a curiosity — it is the reason modern cryptographic key sizes are what they are:

• Breaking RSA keys: QS factored RSA-129 (429 bits) in 1994 after 8 months of distributed work, publicly embarrassing a 1977 bet that it would take 40 quadrillion years.
• Inspiring the GNFS: the relation-matrix idea from QS was directly generalized into the Number Field Sieve, which is still the best known algorithm for large factors and the tool that cracked RSA-768.
• Setting key-size floors: every recommendation to use 2048-bit or 4096-bit RSA keys traces back to complexity analyses built on QS and GNFS running times.
• Smooth-number theory: the smooth-number estimates QS relies on feed into random factoring algorithms, primality tests, and discrete-log computations — the engine under discrete logarithms and elliptic-curve cryptography.
• Educational value: QS is the cleanest path from "factoring is hard" to "here is why" — it makes the sub-exponential gap tangible and shows how linear algebra over $\mathbb{F}_2$ can crack a number-theory problem.

Understand the Quadratic Sieve and you hold the key to why factoring is believed hard — and what it would mean for cryptography if it were not.

The Quadratic Sieve is a beautiful idea at the boundary of possibility. It does not factor by dividing — it factors by finding coincidences, turning a number-theory problem into a linear-algebra problem that a computer can solve in sub-exponential time.

Its legacy lives in every TLS handshake: the 2048-bit RSA minimum exists because QS and its descendant, the GNFS, are the fastest tools we have — and they are still far slower than polynomial. If someone found a polynomial-time factoring algorithm tomorrow, the world's encrypted traffic would crumble overnight.

Until that day, the Quadratic Sieve stands as proof that mathematics can shave an exponential down to sub-exponential — and a reminder that shaving it all the way to polynomial remains the open question behind P vs NP.