How Q-Day Breaks Everything: Shor's Algorithm and the Simultaneous Fall of RSA, Diffie-Hellman, and ECC

1. One Break, Four Falls#

Four cryptographers, working in four different decades on four different branches of mathematics, built the fortresses that guard almost every secret you have ever sent: a 2048-bit RSA key, a 2048-bit Diffie-Hellman group, a DSA signature, and a 256-bit elliptic curve. They look nothing alike -- different keys, different math, different inventors -- so we deployed them side by side and called it diversity.

This article is about the afternoon a single machine running a single idea knocks all four down at once, while AES-256 in the field next door barely looks up -- and about why the reason those four fall together is exactly the reason the fifth survives.

Here is the thesis, stated plainly before any mathematics arrives to defend it: the four are not four problems. They are one. Underneath RSA's factoring, Diffie-Hellman's discrete logarithm, DSA's signatures, and elliptic-curve cryptography's smaller keys lies a single shared object -- a hidden period in a finite abelian group. A quantum computer running Peter Shor's 1994 algorithm reads that period more or less in one shot, and when the period falls, all four fortresses built on top of it fall with it ^[1].

Symmetric cryptography survives for the mirror-image reason: a well-built cipher hides no period at all, so there is nothing for the same machine to read.

The event has a name.

Two questions organize everything that follows, and the whole article is their answer: why do these four fall together? and why not AES? Hold both in your head. The first is a story about a hidden unity nobody designed on purpose. The second is a story about a boundary so sharp it can be stated as a theorem -- and that same boundary turns out to be the entire design premise of the cryptography we are now scrambling to deploy.

RSA, Diffie-Hellman, DSA, and elliptic curves were never four independent bets. They are one bet -- that a hidden period in a finite abelian group is hard to find -- made four times in four disguises. Shor's algorithm collects on all four at once.

One honesty flag, planted here and never lowered: no such machine exists in 2026. Not almost, not in a lab somewhere -- none. The best error-corrected hardware yet demonstrated encodes about one reliable logical qubit ^[2], and a real attack needs on the order of a thousand of them holding still for hours. So this is a loaded gun on the table, not a fired one. That gap between a proven algorithm and an unbuilt machine is not a reason to relax; as we will see, it is precisely the deadline.

The journey runs in seven moves: how the world came to trust just two hard problems, the one quantum trick that matters, the breakthrough that turned factoring into period-finding, the same trick applied three more times, the asymmetry that spares AES, the machine's true price tag, the limits of the blast radius, and why one proven fact already forces a global migration. To see why one machine breaks four fortresses, you first have to see how the world ended up trusting just two hard problems in the first place.

2. Two Problems the Whole World Rested On#

Rewind to 1976. Two strangers want to agree on a shared secret while an eavesdropper records every bit that passes between them. For millennia this was considered impossible: to share a secret you first had to share a secret. Then Whitfield Diffie and Martin Hellman published a construction that let the two strangers mix public numbers into a private one the eavesdropper could not reconstruct, and modern cryptography was born ^[3]. Its security rested on a new assumption -- that one specific arithmetic operation is easy forward and hard backward.

A year later, Ron Rivest, Adi Shamir, and Leonard Adleman turned a different one-way asymmetry into a full encryption-and-signature system: multiplying two large primes is easy, but factoring their product back into those primes is hard ^[4]. RSA bet its life on integer factoring; Diffie-Hellman had bet on the discrete logarithm. Two bets, two problems.

Then the bets consolidated. In 1985 Victor Miller, and independently in 1987 Neal Koblitz, moved the discrete logarithm onto elliptic curves, where the best known classical attacks are far weaker and so the keys can be dramatically smaller for the same classical security ^[5][6]. Elliptic-curve cryptography was not a new hard problem -- it was the same discrete logarithm relocated to a group where classical attackers had less traction. This is the seed of a cruel irony we will harvest in Section 5. ECC's whole selling point is that it achieves equal classical security with smaller keys, because no sub-exponential attack like index calculus applies to well-chosen curves ^[6]. Against a quantum computer, "smaller keys" means "fewer qubits to attack," so the classical strength inverts into a quantum liability.

By the 1990s the accounting was stark. Strip away the packaging and essentially all deployed public-key cryptography reduced to exactly two hard problems: integer factoring and the discrete logarithm. The classical attacks that calibrate their key sizes -- the general number field sieve for factoring, index calculus for finite-field discrete logs, Pollard's rho for elliptic curves -- are the subject of this series' earlier posts on RSA and the discrete logarithm, and I will not re-derive them here ^[7].

What matters is the structural fact: the entire public-key world put all its eggs in two baskets, and nobody chose those two baskets because they were secretly connected. They looked like independent bets.

Nobody chose factoring and the discrete logarithm because they were related. They looked like two independent bets. They were the same bet.

While the defense lineage was consolidating, a second, unrelated lineage was quietly assembling the machine that would read both. In 1982 Richard Feynman observed that simulating quantum physics on a classical computer seems to require exponential resources, and proposed turning the problem around: build a computer that is quantum-mechanical and let physics do the bookkeeping ^[8]. In 1985 David Deutsch made the idea rigorous, defining the universal quantum computer and the principle that it could simulate any physical process ^[9].

This was pure physics and computability theory. Nobody in 1985 thought it had anything to do with RSA. The two lineages were on tracks that had not yet touched.

flowchart LR
subgraph Defense["Defense lineage -- the fortresses"]
DH["1976 Diffie-Hellman: discrete log assumption"]
RSA["1977 RSA: integer factoring"]
ECC["1985 to 1987 Miller and Koblitz: elliptic curves"]
end
subgraph Attack["Attack lineage -- the machine"]
FEY["1982 Feynman: simulate physics with a quantum computer"]
DEU["1985 Deutsch: universal quantum computer"]
SIM["1994 Simon: period-finding template"]
end
DH --> SHOR["1994 Shor: period-finding topples all four"]
RSA --> SHOR
ECC --> SHOR
FEY --> DEU
DEU --> SIM
SIM --> SHOR
SHOR --> GID["2021 to 2025 Gidney: concrete qubit bill"]

Two problems, one machine, a decades-long collision course -- and in 1994 a single person connected them. The bridge between the two lineages started as one strange little algorithm about a hidden XOR mask, and to understand how it grew into the break, you have to understand the one quantum trick that makes all of this work.

3. The One Trick That Matters#

Before we can watch four fortresses fall, we have to kill a myth, because the myth predicts the wrong outcome. The popular story says a quantum computer "tries all the keys at once and reads out the winner." If that were true, it would break AES just as easily as RSA -- every symmetric cipher would fall too, and the entire second half of this article would be wrong. It is not true. A quantum computer does something far stranger and far more specific, and the specificity is the whole point.

Start with the one genuinely non-classical resource.

This is where the myth breaks. Yes, you can evaluate a function on all $2^n$ inputs at once. No, you cannot read the answers. Measurement hands you a single random input-output pair, which is no better than guessing. Superposition alone buys you nothing. The art -- the entire art of quantum algorithms -- is what you do to the amplitudes before you measure.

The tool for that is interference. Amplitudes are complex numbers, and like waves they can add or cancel. If you can arrange the computation so that every path leading to a wrong answer is met by another path of opposite sign, the wrong answers cancel to near-zero amplitude, while the right answers reinforce. Measurement then returns a useful outcome with high probability -- not because you searched, but because you sculpted the wavefunction so that only the structure you care about is left standing.

So which structure can interference exploit? The most powerful answer known is periodicity. Suppose a function $f$ is periodic: it repeats with some hidden period $r$, so that $f(x)$ and $f(x + r)$ always agree. Evaluate $f$ over a superposition of all inputs, and the state quietly organizes itself around that period. The instrument that reads it is the quantum Fourier transform.

Put those pieces together and you have a machine that does exactly one magical thing: it takes a function with a hidden period and hands you that period. Superpose over all inputs, evaluate the function, and the act of computing it entangles the input register with the output so that the input register's amplitudes now repeat with the function's period. Apply the QFT, and interference collapses that repeating pattern onto its frequency. Measure, and you read out information about $r$ -- the period no classical observer could see without effectively checking the inputs one by one.

flowchart TD
A["Superpose over all inputs x"] --> B["Evaluate f(x) into a second register"]
B --> C["Measuring or entangling leaves the input register repeating with period r"]
C --> D["Quantum Fourier transform concentrates amplitude on multiples of 1 over r"]
D --> E["Measure: read a multiple of the hidden frequency"]
E --> F["Classical post-processing recovers r"]

A quantum computer does not search in parallel and read the winner. It engineers interference so that wrong answers cancel and only a function's hidden period survives measurement. No period, no exponential speedup -- which is precisely why the same machine that shatters RSA cannot touch a well-built symmetric cipher.

The first person to turn this into a concrete algorithm was Daniel Simon. In 1994 he built a toy problem -- a function that secretly satisfies $f(x) = f(x \oplus s)$ for a hidden bit-string $s$ -- and showed that quantum interference recovers $s$ exponentially faster than any classical method possibly could ^[11]. Simon's algorithm is the direct ancestor Shor read. Its "period" is a hidden XOR mask in a group of bit-strings, which breaks nothing anyone deployed. Shor's leap was to see the same template hiding inside a problem the entire economy depended on, and to swap Simon's simple transform for the QFT over the integers modulo $N$ ^[11].

Simon's hidden period lived in a toy group and broke nothing real. But it proved the template: encode a secret as the period of a function, then let interference read it. The question that ended an era was the obvious next one -- what real, deployed, load-bearing problem is secretly period-finding in disguise?

4. The Breakthrough: Factoring Is Period-Finding#

In 1994, at Bell Labs, Peter Shor answered that question with a move so clean it still reads like sleight of hand. Factoring -- the problem RSA stakes its life on -- is secretly a period-finding problem. Watch the reduction before the machinery, because the reduction is the whole trick.

To factor a large number $N$, pick a random integer $a$ with no common factor with $N$. Now consider the innocent-looking function $f(x) = a^x \bmod N$. Because there are only finitely many residues modulo $N$, this function must eventually repeat, and it repeats with a period: the smallest $r$ for which $a^r \equiv 1 \pmod N$. That period has a name.

Here is why the order cracks the factorization. Suppose $r$ is even. Then $a^r - 1 = (a^{r/2} - 1)(a^{r/2} + 1)$ is divisible by $N$. Unless $a^{r/2} \equiv -1 \pmod N$ (a case you detect and retry), neither factor on the right is a multiple of $N$ by itself, so each shares only part of $N$'s prime structure. Computing $\gcd(a^{r/2} \pm 1,\, N)$ with Euclid's ancient algorithm then hands you a non-trivial factor. For a random $a$, this works with probability at least one-half, so a couple of tries suffice ^[1].

Every step in that paragraph is classical arithmetic you can run right now -- except one: finding the order $r$. That single sub-problem is where the quantum computer earns its keep, and it is period-finding exactly as Section 3 described it.

Superpose over all exponents $x$, compute $a^x \bmod N$ reversibly into a second register (this modular exponentiation is the dominant cost of the whole circuit), and the first register is left repeating with period $r$. Apply the QFT, and amplitude concentrates on multiples of $1/r$; measure, and you get an estimate of some $k/r$. A classical continued-fraction expansion then recovers $r$ from that estimate.

flowchart TD
A["Pick random a in the range 2 to N minus 1"] --> B{"a coprime to N?"}
B -->|no| Z["gcd(a, N) is already a factor -- lucky"]
B -->|yes| C["Quantum step: find the order r of a mod N by QFT period-finding"]
C --> D["Classical step: continued fractions recover r from the measured fraction"]
D --> E{"r even and a^(r/2) not -1 mod N?"}
E -->|no| A
E -->|yes| F["Classical step: gcd(a^(r/2) +/- 1, N) yields a non-trivial factor"]

You do not need a quantum computer to see the reduction work, because only the order-finding is quantum. Compute the order by brute force on a small $N$, feed it into the same greatest-common-divisor step Shor uses, and a real factor drops out.

from math import gcd

def find_order(a, N):
  # multiplicative order of a mod N: smallest r >= 1 with a^r = 1 (mod N)
  x = a % N
  r = 1
  while x != 1:
      x = (x * a) % N
      r += 1
      if r > N:                # safety: a was not coprime to N
          return None
  return r

def factor_via_order(N, a):
  if gcd(a, N) != 1:
      return gcd(a, N), N // gcd(a, N)     # lucky: a already shares a factor
  r = find_order(a, N)
  if r is None or r % 2 != 0:
      return None                           # r odd -> pick another a and retry
  y = pow(a, r // 2, N)
  if y == N - 1:
      return None                           # a^(r/2) = -1 mod N -> retry
  return gcd(y - 1, N), gcd(y + 1, N)

for (N, a) in [(15, 7), (21, 2), (2047, 5)]:
  print("N =", N, " a =", a,
        " order r =", find_order(a, N),
        " factors =", factor_via_order(N, a))
# N = 15  a = 7  order r = 4  factors = (3, 5)
# N = 21  a = 2  order r = 6  factors = (7, 3)
# N = 2047 a = 5  order r = 44 factors = (23, 89)

The classical order search above is exponential in the number of digits -- run it on a 2048-bit $N$ and it never returns. Shor's contribution is to replace that one line with a quantum circuit that finds the same $r$ in polynomial time. Alexei Kitaev reformulated the quantum step in 1995 as phase estimation on the operator that multiplies by $a$, recovering $r$ from the eigenvalue's phase. It is mathematically equivalent to Shor's order-finding and is how most modern textbooks present the algorithm ^[12]. How polynomial? The whole circuit is about $O((\log N)^3)$ gates, dominated by the modular exponentiation; the QFT itself is only $O((\log N)^2)$ ^[10].

One precision point, flagged loudly because it will haunt Sections 7 and 8: that $O((\log N)^3)$ is a circuit size on a perfect, noiseless, fault-tolerant machine. It counts logical gates, not seconds. The distance between "a polynomial-size circuit exists" and "a machine ran it before lunch" is measured in millions of physical qubits, and we will pay that bill in full later.

Now the consequence that inverts fifty years of defensive instinct.

Shor's cost grows with the logarithm of the key, not the key. Against this attack, RSA-4096 is not meaningfully safer than RSA-2048 -- it is a rounding error safer.

Factoring was the first fortress to fall. But Shor's 1994 paper had a second half that almost nobody quotes, and it is the reason Diffie-Hellman, DSA, and elliptic curves fall too -- not by coincidence, but by the same mechanism running one dimension higher.

5. The Same Trick, Three More Times#

If factoring is secretly period-finding, the natural question is: what else is? The answer is the entire argument of this article. Almost everything the deployed public-key world rests on is period-finding in disguise -- and Shor's own 1994 paper proved the second case himself.

Recall the discrete logarithm: given $g$ and $h = g^s$ in a cyclic group of order $r$, recover the exponent $s$. Shor's insight was that $s$ is also hidden inside a periodicity, only now the period lives in two dimensions instead of one. Here is the mechanism in full, because it is the load-bearing step and hand-waving it would cheat you of the aha.

Define the two-variable function

$f(x, y) = g^x \, h^y = g^{\,x + s y}.$

This function takes the same value whenever the exponent $x + s y$ is unchanged modulo $r$. So the set of shifts that leave $f$ invariant -- its hidden period, now a lattice of vectors rather than a single number -- is

$L = \{(x, y) \in \mathbb{Z}^2 : x + s y \equiv 0 \pmod{r}\}.$

That lattice encodes the secret $s$ directly in its slope. To read it, Shor superposes over both exponent registers and applies a two-dimensional QFT. Interference concentrates the amplitude onto the dual frequency vectors $(k_1, k_2)$ satisfying $k_1 + s\,k_2 \equiv 0 \pmod{r}$. A single measurement returns one such pair, and whenever $\gcd(k_2, r) = 1$ you solve for the secret in one line of classical arithmetic:

$s \equiv -\,k_1 \, k_2^{-1} \pmod{r}.$

Look at what just happened. This is the exact same period-extraction that factored $N$ in Section 4 -- superpose, evaluate, transform, measure, post-process -- run in two dimensions instead of one ^[1]. The discrete logarithm does not resist Shor any harder than factoring does; it surrenders the secret exponent directly. Finite-field Diffie-Hellman, DSA, and ElGamal all rest on precisely this discrete logarithm, so all three fall in the same stroke.

Elliptic curves are the same story one more time. The points on an elliptic curve form a finite abelian group under a geometric addition law, and "discrete logarithm" there means recovering the integer $s$ with $Q = sP$ for public points $P$ and $Q$. It is the same $f(x,y)$, the same two-dimensional period, the same 2-D QFT -- only the group operation changes. John Proos and Christof Zalka worked out the elliptic-curve version explicitly in 2003, and with it ECDH, ECDSA, and EdDSA join the list ^[13].

Now the unification that turns three coincidences into one sentence.

Alexei Kitaev supplied this abstraction in 1995 ^[12]. Before it, "Shor breaks RSA" and "Shor breaks Diffie-Hellman" looked like two separate results that happened to use the same author's trick. After it, they are two instances of a single mathematical fact: the quantum Fourier transform reads a hidden period in any finite abelian group. Factoring hides its period in one dimension; both discrete logs hide theirs in two; the machine does not care which.

flowchart TD
F1["Integer factoring -- RSA"] --> HSP["Abelian hidden subgroup problem: f is constant on the cosets of a hidden subgroup"]
F2["Finite-field discrete log -- DH and DSA"] --> HSP
F3["Elliptic-curve discrete log -- ECDH and ECDSA"] --> HSP
HSP --> QFT["Quantum Fourier transform reads the hidden period"]
QFT --> O1["RSA falls"]
QFT --> O2["Diffie-Hellman and DSA fall"]
QFT --> O3["ECDH and ECDSA fall"]

The four are not four security problems. They are one -- a hidden abelian period -- wearing four disguises. Factoring hides it in one dimension; the two discrete logs hide it in two. One machine, one idea, four falls.

Two precautions before the table. First, "together" means the same machine class and the same breakthrough, not one identical circuit pressing a single button. RSA, a finite field, and an elliptic curve need different arithmetic units compiled into the machine; what they share is that each reduces to the abelian HSP, so one fault-tolerant quantum computer running Shor's family of circuits dispatches all of them. Second -- and this is the counterintuitive kicker -- the four do not fall in the order their reputations suggest. Elliptic-curve cryptography, the strongest of the four against classical attack, falls first.

Why? Because ECC's classical strength is small keys. No sub-exponential attack applies to a well-chosen curve, so a 256-bit elliptic key matches the classical security of a 3072-bit RSA key ^[14]. Against Shor, "fewer bits" simply means "fewer logical qubits to build."

Martin Roetteler and colleagues estimated in 2017 that breaking the NIST P-256 curve needs about 2330 logical qubits ^[15] -- materially fewer than the roughly 6200 logical qubits (about $3n$) a 2048-bit RSA break requires ^[16]. Proos and Zalka had already found the same inversion in 2003: about 1000 qubits for 160-bit ECC versus about 2000 for the security-equivalent 1024-bit RSA ^[13]. Those small keys also pay a purely classical dividend that has nothing to do with quantum computers: at equal classical security an ECC certificate and its handshake messages are a fraction of the size of the RSA equivalent, which trims bandwidth and storage on every connection they protect.

"ECC is an easier target than RSA." -- Roetteler, Naehrig, Svore, and Lauter, 2017

The full ledger, with the survivor included so the contrast is unmissable:

Three rows share the "yes" column, and that shared "yes" is the entire vulnerability. One machine, one idea, four falls -- and yet AES-256 in the field next door survives untouched. That survival is not luck, and it is not a gap someone will patch next year. It is the second half of the thesis, and it has a proof.

6. Why Symmetric Crypto Only Loses a Square Root#

Return to AES-256, standing untouched in the next field. The same machine that reads RSA's period in polynomial time barely dents it. The reason is exactly the reason RSA falls: AES hides no period. There is no abelian structure inside a well-designed cipher for the QFT to grab, so the exponential engine has nothing to bite on. What is left is the generic attack that works on any search problem, structured or not.

At a glance that looks alarming -- $2^{64}$ sounds within reach. Hold that thought; it is the most misunderstood number in the field, and we will dismantle it in a moment. First, the structural point, because it is what makes the symmetric world safe by design rather than by luck.

The quadratic speedup is not a weak version of Shor's exponential one. It is a different kind of thing, and its weakness is provable. Bennett, Bernstein, Brassard, and Vazirani proved in 1997 that any quantum algorithm searching an unstructured space needs at least on the order of $\sqrt{N}$ queries -- the $\Omega(\sqrt{N})$ lower bound ^[17]. Grover is optimal; you cannot do better against a structureless target.

This is the single most important bound in the article, because it converts "we do not know a better attack on AES" into "there provably is no better generic attack." Shor exists because factoring has structure. Grover is the best you can ever do precisely when there is none.

// Classical brute force is 2^n; Grover's floor is 2^(n/2).
// This compares EXPONENTS -- it is a query lower bound, not a runtime.
function keyStrength(nBits) {
return { classical: nBits, grover: nBits / 2 };  // log2 of each cost
}

for (const n of [128, 192, 256]) {
const s = keyStrength(n);
console.log("AES-" + n + ": classical 2^" + s.classical + " vs Grover floor 2^" + s.grover);
}

// Doubling the key restores the pre-quantum margin:
const groverAes256 = keyStrength(256).grover;      // 2^128
const classicalAes128 = keyStrength(128).classical; // 2^128
console.log("AES-256's Grover floor 2^" + groverAes256 +
          " equals AES-128's old classical margin 2^" + classicalAes128);
// AES-128: classical 2^128 vs Grover floor 2^64
// AES-256: classical 2^256 vs Grover floor 2^128

So doubling the key exactly undoes Grover: AES-256's $2^{128}$ Grover floor restores the $2^{128}$ margin AES-128 used to enjoy classically. But "double the key" undersells how safe AES-128 already is, and here is where the popular $2^{64}$ falls apart.

That $2^{64}$ is a floor on operations, not a feasible runtime. Three facts, each independently decisive, separate the number from any real attack. First, Grover is inherently sequential: its roughly $2^{n/2}$ iterations must be applied one after another, and each iteration contains a full evaluation of AES as a reversible quantum circuit -- a deep block of gates, not a single step ^[19]. You cannot collapse the iterations into a shallow parallel circuit.

Second, it barely parallelizes: split the search across $P$ machines and each one's work drops by only $\sqrt{P}$, not $P$. Christof Zalka proved this is fundamental -- quantum searching "cannot be parallelized better than by assigning different parts of the search space to independent quantum computers" ^[20]. Throwing a thousand quantum computers at AES-128 buys a factor of about 31, not 1000.

Third, and most concrete: real machines have a maximum circuit depth. NIST's post-quantum call formalized this as MAXDEPTH, with plausible values of $\{2^{40}, 2^{64}, 2^{96}\}$ serial logical gates -- roughly a year, a decade, and a millennium of continuous computation. Under that constraint, NIST estimated the cost of a Grover key search on AES-128 at about $2^{170}/\text{MAXDEPTH}$ quantum gates, versus $2^{143}$ classical gates -- because "one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramatic" ^[21].

Even with MAXDEPTH at a decade ($2^{64}$), that is about $2^{106}$ gates. Depth-restricted analyses of explicit AES Grover oracles confirm the picture and underpin NIST's security categories ^[22]. The clean $2^{64}$ was always a lower bound on abstract queries, never a wall-clock estimate.

The comparison, side by side:

One honest fence marks the edge of that "only Grover" claim.

So the break is real, the boundary is sharp, and the algorithm has been proven on paper for thirty years. Only one thing still stands between the mathematics and your ciphertext: a machine that does not yet exist. Building it is where the story turns from algorithms to engineering -- and where the price tag appears.

7. From Algorithm to Machine: Fault Tolerance and the Qubit Bill#

A polynomial-time algorithm is not a polynomial-time afternoon. Shor's circuit is small on paper, but "on paper" assumes qubits that never make a mistake and never forget. Real qubits do both, constantly. Run a bare Shor circuit on today's noisy hardware and it dissolves into random noise long before the modular exponentiation finishes. Closing the gap between the proof and the machine is an engineering problem measured in millions of qubits, and it has a structure worth understanding, because that structure is where the cost estimates come from -- and where they are falling.

Begin with the distinction the whole field turns on.

The manufacturing method is quantum error correction, and the workhorse is the surface code.

Error correction handles the memory and the easy gates, but Shor also needs "non-Clifford" gates -- the T and Toffoli operations that do the genuinely quantum arithmetic -- and those cannot be done directly on surface-code qubits. They are supplied through a separate factory that distills noisy inputs into clean "magic states." The modern version of that factory is magic-state cultivation, which reaches logical error rates as low as $2 \times 10^{-9}$ under $10^{-3}$ circuit noise and, in its authors' words, hints that "further magic state distillation may never be needed in practice" -- shaving one of the largest overheads in the whole bill ^[24]. Stack it all together and you get the fault-tolerance pyramid every estimate rests on.

flowchart TD
P["Thousands of noisy physical qubits, about 1 percent error each"] --> S["Surface-code patch: parity checks suppress errors exponentially in code distance"]
S --> L["One reliable logical qubit"]
M["Magic-state cultivation: clean T and Toffoli states"] --> G["Non-Clifford gates that Shor requires"]
L --> G
G --> SHOR["Fault-tolerant Shor circuit: about 3n logical qubits, billions of gates"]

Now the part that reframes the entire threat. Line up the resource estimates chronologically and hold the hardware assumptions fixed, and you see the price of Q-Day collapsing -- not because anyone built a better qubit, but because the algorithms kept improving.

Read the last three rows slowly. In 2021 Craig Gidney and Martin Ekera published the first end-to-end physical estimate: about 20 million noisy physical qubits, 8 hours, assuming a surface code with $10^{-3}$ gate error, a microsecond cycle time, ※ A surface-code cycle is one full round of parity measurement across the patch; the estimate assumes roughly one microsecond per round, so an 8-hour run is on the order of tens of billions of rounds. and short-discrete-log refinements from Ekera and Hastad folded in ^[16][28].

In 2023 Oded Regev found the first asymptotic reduction in Shor's gate count in three decades -- roughly $O(n^{3/2})$ gates -- though he flagged it as resting on a heuristic and not clearly practical, and its variant trades gate count for extra space whose real-world cost is still unsettled ^[26]. Then in 2025 Gidney returned with a new estimate: fewer than one million physical qubits, under a week -- and, in a line worth pausing on, the same 2019 hardware assumptions he used in the 20-million estimate ^[27].

Twenty million qubits to under one million in six years -- same author, same hardware assumptions, one-twentieth the machine. The mathematics improved, not the metal.

That drop happened with no improvement in the underlying qubits at all: the estimate, not the machine, was the moving part, which means the cost of Q-Day keeps falling on the strength of pure algorithm design, independent of when good hardware arrives. That is the uncomfortable dynamic hiding behind every "quantum is decades away" headline: the target keeps moving toward us on the math axis while we wait for the hardware axis. The algorithm's price tag is collapsing on its own schedule. So the only question left is the one everyone actually asks -- how close is the machine itself?

8. Where the Hardware Actually Is (and Isn't)#

State the honesty anchor flatly, because everything downstream depends on it: as of 2026, no cryptographically relevant quantum computer exists. Not "almost," not "in a classified lab somewhere." None. The public state of the art is three to four orders of magnitude short of a Shor attack, and it helps to see exactly how short, because the headlines and the reality use the same words to mean different things.

The state of the art splits cleanly into two regimes, and conflating them is the source of most confusion. The first is fully below-threshold error correction -- the hard, scalable kind, where adding qubits genuinely drives the error down.

Google's Willow is the reference point: a distance-7 surface-code patch, a 7-by-7 array of 49 data qubits totaling 101 physical qubits, encoding exactly one logical qubit. The logical error is suppressed by a factor $\Lambda = 2.14 \pm 0.02$ for each two-step increase in code distance, and its lifetime beats its best physical qubit by 2.4 times ^[2]. That $\Lambda$ greater than 1 is the whole result: it is the first convincing demonstration that a real surface code operates below threshold, so that making the patch bigger makes the logical qubit better rather than worse. The number to remember is the ratio: about 100 physical qubits for one good logical qubit, today ^[2]. So the scalable frontier stands at roughly one logical qubit built from about a hundred physical ones.

The second regime is error detection at low code distance, and it is where the "tens of logical qubits" headlines come from. A neutral-atom processor from a Harvard, MIT, and QuEra collaboration entangled up to 48 logical qubits using small [[8,3,2]] code blocks (alongside 40 color-code qubits and a surface-code logical operation scaled across code distances) on up to 280 physical qubits ^[29]. That is a genuine milestone -- but these are transversal, post-selected error-detection demonstrations, which throw away runs where an error is spotted, not a scalable below-threshold memory that can run for billions of gates.

On the trapped-ion side, Quantinuum ran a handful of logical qubits with full repeated error correction: a [[7,1,3]] code and a [[12,2,4]] code based on Knill's C4/C6 scheme (two logical qubits), the first reaching error rates 9.8 to 500 times below the physical rate and the second 4.7 to 800 times below it ^[30].

Put the three numbers next to the requirement and the chasm is obvious. Fully below-threshold correction reaches about one logical qubit on superconducting hardware and a couple on trapped ions; error detection reaches a few tens on neutral atoms.

A CRQC needs about 2330 logical qubits for the P-256 curve ^[15], or roughly $3n$ -- at least 6200 -- for RSA-2048, backed by fewer than a million physical qubits ^[27]. Between "48 post-selected logical qubits in a detection demo" and "a few thousand fully corrected logical qubits running Shor for hours" lie three to four orders of magnitude and several unsolved engineering problems.

When, then? The honest answer is a window, not a date. Expert judgment clusters the arrival of a CRQC in roughly the 2030 to 2035 range with wide uncertainty on both sides. The most-cited proxy, the Global Risk Institute and evolutionQ expert-survey timeline, reports figures on the order of 28 to 49 percent probability within ten years ^[31] -- but that number must be quoted with its qualifier: it is a survey of expert opinion, not a measured or primary-verified quantity, and the defensible claim is the qualitative window, not any single percentage.

The gun is loaded and sitting on the table. Its trigger is an engineering trajectory, not a delivered capability, and the timeline is a judgment rather than a promise -- but a judgment that says "sometime in the next decade" is not a judgment you can safely ignore for data that must stay secret into the 2040s. Before we talk about who has to move first, one question decides everything downstream: what, exactly, does this machine not break?

9. What Q-Day Does Not Break#

The blast radius is bounded, and the boundary is the thesis restated as a theorem: Shor breaks exactly the abelian-hidden-subgroup primitives, and nothing else structurally. Everything on the safe side of that line survives Q-Day, and a whole field of cryptography was deliberately built there.

Start the inventory. Symmetric ciphers and hashes survive with only Grover's quadratic nibble, as Section 6 proved. Hash-based signatures such as SLH-DSA rest on nothing but the preimage and collision resistance of a hash function, so they inherit that same square-root safety and no more ^[32]. And the new public-key families -- lattices, codes, isogenies, multivariate systems -- survive because not one of them is an abelian hidden-subgroup problem. The QFT has no period to read.

The sharpest way to say why is to name the structure lattices actually touch.

Notice the symmetry. The abstraction that unifies the attack -- the abelian HSP -- is the very same abstraction that bounds it. Cross from abelian to non-abelian structure and the QFT stops working, Shor's polynomial-time guarantee evaporates, and the best anyone has managed in twenty years is sub-exponential. That single conceptual line is the design premise of post-quantum cryptography.

But here precision matters more than anywhere else in the article, because the most natural way to summarize this is wrong and plants a misconception. It is tempting to write that the best quantum attack on lattice schemes is Kuperberg's sub-exponential algorithm. It is not, for three reasons worth stating explicitly.

First, the attack that actually sets lattice key sizes is not a hidden-subgroup attack at all. It is lattice sieving -- quantum-accelerated BKZ -- and it is exponential. Heuristic quantum sieving for the shortest-vector problem runs in about $2^{0.312n + o(n)}$, against the classical $2^{0.384n + o(n)}$ ^[34]. Quantum search shaves the constant in the exponent; it never reaches sub-exponential. Lattice parameters are chosen against that exponential wall.

Second, the famous link between lattices and the dihedral HSP is a one-directional reduction, not a usable attack. Regev showed in 2004 that a dihedral-HSP solver by coset sampling would break the unique shortest-vector problem ^[35] -- but there is no known way to prepare the required dihedral coset states from an actual lattice instance. The implication runs from "hypothetical dihedral solver" to "broken lattice," not the other way, so you cannot feed a real lattice problem into Kuperberg's algorithm and get an attack out.

Third, Kuperberg's sub-exponential algorithm genuinely is the best known attack -- but for a different family. Commutative-isogeny schemes like CSIDH are built on an abelian group action, a hidden-shift problem, and there Kuperberg's algorithm really does set the parameters ^[36][33]. The "Kuperberg" label belongs on a CSIDH row, never on the lattice row. With that fixed, here is the honest ledger of what falls and what stands.

The line Shor cannot cross is the line between abelian and non-abelian structure -- and that single line is the entire design premise of post-quantum cryptography. Lattice schemes are not "probably too hard to bother with"; they sit provably on the far side of the abstraction that makes Shor work.

Two counterweights keep this from becoming triumphalism, and they cut in opposite directions.

So Shor is a scalpel, not a bomb. It cuts exactly one structure -- the abelian hidden period -- and a whole field of cryptography was engineered to live on the parts it cannot reach. That field exists for exactly one reason, and with every piece now on the table, it is time to name it.

10. Why This One Event Is the Whole Reason PQC Exists#

Assemble the pieces and one sentence follows that you now have every reason to accept. Because RSA, Diffie-Hellman, DSA, and elliptic-curve cryptography share exactly one crack -- the abelian period the QFT reads -- that crack is not four separate vulnerabilities. It is a single point of failure for nearly the entire deployed public-key world. And a single point of failure of that magnitude does not get patched. It gets routed around, by building a replacement on the far side of the abelian line.

One shared crack under four fortresses is not four vulnerabilities. It is one -- a single point of failure for nearly all deployed public-key cryptography. Post-quantum cryptography is the world's response to that one fact.

That response is already machinery, and every gear traces back to Shor. In 2016 NIST opened a public competition to standardize quantum-resistant algorithms ^[38]; on 13 August 2024 it published the first three standards -- FIPS 203 (ML-KEM) for key establishment, FIPS 204 (ML-DSA) for signatures, and FIPS 205 (SLH-DSA) for hash-based signatures ^[39][40][32].

The NSA's CNSA 2.0 suite sets a national-security transition timeline and, tellingly, keeps AES-256 and SHA-384/512 on the symmetric side because those need no replacement ^[41]. And in 2026 the United States made it binding: Executive Order 14412 requires high-value systems to adopt post-quantum key establishment by 31 December 2030 and post-quantum signatures by 31 December 2031 ^[42].

There is a quiet revival buried in that timeline. The lattice hardness now anchoring ML-KEM and ML-DSA is not new: Miklos Ajtai put worst-case lattice hardness on a rigorous footing in 1996, and NTRU shipped a ring-based lattice cryptosystem in 1998 ^[43][44]. Both sat in a niche for two decades. What changed their fortunes was not a new theorem -- it was Shor turning "hardness the quantum Fourier transform cannot read" into the single most valuable property a cryptosystem can have, and a generation of survey work mapping out the lattice, code, hash, and isogeny families that possess it ^[7].

But standards and deadlines only matter if they beat the clock, and the clock is subtle, because it started ticking before the machine exists. Michele Mosca captured the logic in a single inequality.

flowchart LR
X["X: years to migrate"] --> SUM["X + Y"]
Y["Y: years data must stay secret"] --> SUM
Z["Z: years until a CRQC exists"] --> CMP{"X + Y greater than Z?"}
SUM --> CMP
CMP -->|yes| EXP["Already exposed: harvested ciphertext will be readable"]
CMP -->|no| OK["Safe, for this data, for now"]

The inequality has teeth because of the harvesting strategy that makes $Z$ irrelevant for confidentiality.

This is the hinge of the whole series, so state it without hedging. The post-quantum migration is not a bet on when quantum computers will arrive. It is a response to one already-proven mathematical fact -- that Shor's algorithm reads the shared abelian period under RSA, Diffie-Hellman, DSA, and ECC -- combined with one strategic fact, that adversaries can harvest today and decrypt later. Neither of those facts depends on a machine booting up. Which means the work starts now, not on Q-Day. So what, concretely, do you do before the machine that does not yet exist finally does?

11. What To Do Before Q-Day#

You cannot buy a cryptographically relevant quantum computer, and you cannot wait for one to appear before acting -- harvest-now-decrypt-later has already seen to that. The good news is that the pre-Q-Day checklist follows directly from the thesis, and every item on it is doable today with shipping standards.

1. Inventory every use of RSA, DH, DSA, ECDH, and ECDSA. Build a cryptographic bill of materials: where each algorithm lives, which keys protect what, and how long each secret must last. This is not busywork. Because all four primitives share one crack, nothing on that list is safe by virtue of key size, curve choice, or obscurity -- the inventory is the map of your entire exposure.

2. Triage by secrecy lifetime. Run Mosca's inequality on each data class. Anything whose confidentiality must outlive the CRQC window -- health records, state secrets, long-lived credentials, genomic data -- migrates first, because for that data $X + Y > Z$ already holds ^[45]. You can compute the gap directly.

// If migration time X + secrecy lifetime Y exceeds time-to-CRQC Z, you are exposed.
function mosca(X, Y, Z) {
const exposed = (X + Y) > Z;
const gap = (X + Y) - Z;   // positive gap = years of exposure
return { exposed, gap };
}

const cases = [
{ label: "Long-lived health records", X: 5, Y: 25, Z: 12 },
{ label: "Short-lived session key",   X: 2, Y: 1,  Z: 12 },
];
for (const c of cases) {
const r = mosca(c.X, c.Y, c.Z);
console.log(c.label + ": X=" + c.X + " Y=" + c.Y + " Z=" + c.Z + " -> " +
  (r.exposed ? "EXPOSED by " + r.gap + " years" : "safe by " + (-r.gap) + " years"));
}
// Long-lived health records: X=5 Y=25 Z=12 -> EXPOSED by 18 years
// Short-lived session key: X=2 Y=1 Z=12 -> safe by 9 years

3. Deploy hybrid key establishment now. Combine a classical exchange with a lattice one -- for example the X25519MLKEM768 hybrid -- so that a future CRQC cannot decrypt today's captured sessions, while a flaw in the young post-quantum scheme still leaves the classical layer standing ^[39]. Hybrids are the pragmatic answer to "the abelian period is readable" and "the new assumptions are unproven" at the same time.

4. Migrate signatures on their own timeline. Move to ML-DSA or SLH-DSA, but recognize the urgency differs from confidentiality ^[40][32]. A forged signature requires a CRQC at signing time; there is nothing an adversary can harvest today and forge later. Confidentiality is the harvestable asset, so it leads.

5. Take the cheap symmetric hedge. Prefer AES-256 over AES-128 and SHA-384 or SHA-512 over SHA-256. As Section 6 established, Grover is only quadratic -- and under a realistic depth limit, far weaker than even that -- so doubling the security parameter is sufficient, not merely hopeful ^[17]. This is the one part of the migration that costs almost nothing.

6. Build crypto-agility. Design so the algorithm can be swapped without re-architecting the protocol, so the next transition is a configuration change rather than another decade-long project.

Crypto-agility is doubly warranted here, because the destination assumptions are young. SIDH's classical collapse in 2022 is the standing reminder that a scheme can look quantum-safe and still fail for reasons no one anticipated ^[37]. Agility is how you survive being wrong about the replacement.

For the details of what to migrate to -- parameter sets, performance trade-offs, and deployment patterns -- this series' post-quantum-toolkit and crypto-agility installments carry the load, and the implementation-hardening questions (side channels, fault attacks, and the rest) belong to the empirical sibling, per this article's structural-only contract. None of it waits for the machine. That is the whole point -- and it is why the last few questions people always ask deserve straight, mechanism-grounded answers.

12. Sharp Questions, Straight Answers#

Step back to the single image the whole article was built to earn. Four cryptographers, four decades, four branches of mathematics -- and one hidden period beneath all of them. RSA, Diffie-Hellman, DSA, and elliptic curves were never four independent bets. They were one bet, that a hidden abelian period is hard to find, made four times in four disguises.

Shor's algorithm reads that period with the quantum Fourier transform and collects on all four at once, while AES-256 in the next field survives for the mirror-image reason: it hides no period, so the same machine can do no better than a provably quadratic nibble. That asymmetry -- abelian falls, non-abelian stands -- is not a footnote. It is the exact line post-quantum cryptography was engineered to live behind.

The shared quantum vulnerability of RSA, Diffie-Hellman, DSA, and elliptic curves is a single point of failure, and that single point is the whole reason post-quantum cryptography exists. The algorithm is proven; the machine is not here yet; and the distance between those two facts is not your safety margin -- it is your deadline.

The gun is loaded and on the table. No one has fired it, and no one can say precisely when someone will. But the mathematics that makes it fire was settled in 1994, the price of ammunition is falling every year, and some of the secrets it will read are being recorded right now. That is why the work does not start on Q-Day. It starts today.