The Quantum Threat: Shor's Algorithm and the Q-Day

TL;DR

Traffic encrypted today under RSA or ECC is already exposed to a future adversary, not just a present one — this is the Harvest Now, Decrypt Later (HNDL) threat model: record the ciphertext now, decrypt it once a cryptographically relevant quantum computer (CRQC) exists. Shor's algorithm is why that computer would succeed: it reduces factoring $N = p \times q$ and the elliptic-curve discrete log to a period-finding problem solvable via the quantum Fourier transform in $O((\log N)^3)$ time, against the best classical algorithm's sub-exponential cost. What stands between today and that computer is logical qubits, not the raw physical qubit counts vendors publish — a logical qubit is hundreds to thousands of physical qubits bound together by error correction, and running Shor's algorithm against a 2048-bit key needs on the order of thousands of logical qubits, a threshold current hardware has not reached. Below is a simulator to explore how that gap between physical and logical qubits determines the estimated break time for a given RSA key size.

Harvest Now, Decrypt Later

HNDL does not require an adversary to have a working quantum computer today — only network access and storage. TLS 1.3's forward secrecy, built on ephemeral (EC)DHE, protects recorded traffic against a classical adversary who later steals the server's long-term signing key: the session key was derived from ephemeral secrets that were discarded and never depended on that long-term key. It provides no protection against an adversary who can instead solve the discrete logarithm problem directly from the recorded exchange $g^a \bmod p$, $g^b \bmod p$ — which is exactly what a CRQC running Shor's algorithm does.

The risk is proportional to data lifetime, not to today's decrypt capability. Traffic with a confidentiality requirement measured in years or decades — health records, genomic data, government and military communications, long-lived intellectual property — is already compromised against a sufficiently patient adversary the moment it is encrypted with RSA or ECC, regardless of when Q-Day actually arrives. This is the argument for migrating key exchange to post-quantum algorithms now, ahead of the hardware.

From Factoring to Period-Finding

RSA's classical security rests on the assumed difficulty of recovering $p$ and $q$ from:

The best classical factoring algorithm, the General Number Field Sieve, runs in sub-exponential time in $\log N$. Shor's algorithm avoids factoring $N$ directly and instead solves a related, structurally easier problem: finding the period of a modular exponentiation function. Pick a random $a < N$ coprime to $N$, and define:

This function is periodic: there exists some smallest $r > 0$ such that $f(x + r) = f(x)$ for all $x$. Classically, finding $r$ requires effectively as much work as factoring itself. A quantum computer finds it efficiently by preparing a superposition over all $x$, applying $f$ as a unitary operation across that superposition simultaneously, then applying the quantum Fourier transform to the result — collapsing the superposition onto states that reveal $r$ with high probability on measurement.

Once $r$ is known, and provided $r$ is even and $a^{r/2} \not\equiv -1 \pmod N$ (true for a random $a$ with probability at least $1/2$, so the algorithm is simply retried on failure), the factors fall out of a single GCD computation:

The entire procedure — modular exponentiation, quantum Fourier transform, and classical GCD post-processing — runs in $O((\log N)^3)$ time: polynomial in the bit-length of $N$, against the classical algorithm's sub-exponential cost. This is not a constant-factor speedup; it changes RSA-2048 from "infeasible" to "a matter of qubit count."

Why ECC Falls Too — And Falls Harder

Shor's algorithm is not specific to modular exponentiation — it solves the abelian hidden subgroup problem in general, and both RSA's multiplicative group and an elliptic curve's point-addition group are instances of it. For a curve point $Q = k \cdot P$, the same period-finding structure recovers the scalar $k$: the quantum algorithm treats "elliptic curve discrete logarithm" as another period-finding instance over the curve's group operation instead of modular multiplication.

Because ECC reaches a given classical security level with a much smaller key than RSA (256-bit versus 3072-bit for a 128-bit classical security margin), it also requires fewer logical qubits to break at that same security level. ECC's efficiency advantage against classical attackers becomes a liability against quantum ones — it is the more urgent migration target of the two, not the safer one.

Physical Qubits vs. Logical Qubits

Vendor announcements report physical qubit counts — the raw number of superconducting loops, trapped ions, or other two-level quantum systems on a chip. Physical qubits are noisy: gate error rates on current hardware sit around $10^{-3}$, and a computation as long as Shor's algorithm against a cryptographic-size $N$ requires error rates far below what any physical qubit sustains on its own.

A logical qubit is a fault-tolerant unit built from many physical qubits via a quantum error-correcting code (commonly the surface code), which continuously detects and corrects errors across the group. Depending on the physical error rate and the code distance required to suppress logical error below a usable threshold, current estimates put the overhead at roughly $1{,}000$ to $20{,}000$ physical qubits per logical qubit.

Running Shor's algorithm against a 2048-bit RSA key is estimated to require on the order of thousands of logical qubits with sufficiently low error rates sustained over the full circuit depth. Current quantum hardware — in the thousands of physical qubits, all still noisy — has not reached the logical qubit count Shor's algorithm needs at cryptographic scale. Q-Day tracks the logical qubit curve, not the physical one, and the gap between the two headline numbers is the actual timeline question.

What This Changes Today

Shor's algorithm doesn't need to run today to be a present threat under the HNDL model — see Shor's Algorithm for the full breakdown of why RSA and ECC specifically fall to it, and Symmetric vs. Asymmetric Encryption for why the web's key exchange depends on exactly the problems Shor's algorithm solves. The response already underway — NIST-standardized lattice-based key encapsulation deployed alongside classical ECDHE in TLS 1.3's hybrid mode — is designed precisely so that today's traffic survives whatever Q-Day's actual date turns out to be.