Shor's Algorithm and the Quantum Threat

Two hard problems, discovered independently, attacked separately for twenty years. In 1994 Peter Shor showed that a quantum computer solves both of them in polynomial time. This note explains what a quantum computer is, what Shor's algorithm exploits, and why the threat is already operational even though the machine does not exist yet.

01.What a quantum computer is

A classical bit is in one of two states, $0$ or $1$. Eight of them hold one of $256$ possible values, one value at a time.

A quantum bit, or qubit, is different. Its state is described by two numbers called amplitudes, one attached to $0$ and one attached to $1$, and both can be non-zero at once. That condition is called superposition. Writing $\alpha$ for the amplitude on $0$ and $\beta$ for the amplitude on $1$, the state is written

$$\alpha \,|0\rangle \;+\; \beta \,|1\rangle,$$

where the bracket notation is just a label saying which outcome the amplitude belongs to. The rule connecting this to reality is that if you measure the qubit you get $0$ with probability $|\alpha|^2$ and $1$ with probability $|\beta|^2$, and those two probabilities add to $1$.

The first thing everyone hears about quantum computing is that $n$ qubits hold all $2^n$ combinations at once, so a quantum computer tries every possibility in parallel. That is half true and the missing half is the important one.

It is true that $n$ qubits carry $2^n$ amplitudes. It is false that this gives you $2^n$ answers, because measurement returns exactly one outcome, chosen at random according to those probabilities. If you put a computation into superposition over a million inputs and then measure, you get one input's answer, picked at random. You could have done that by guessing.

02.Interference is where the power actually is

The property that makes quantum computers useful is the second one: amplitudes can be negative, or more generally complex, and so they can cancel.

Two contributions arriving at the same outcome with amplitudes $+0.5$ and $-0.5$ sum to zero, and that outcome is then never observed. This is interference, and it is the same phenomenon as two water waves meeting crest to trough and flattening.

So a quantum algorithm is not a parallel search. It is a carefully engineered interference pattern. You arrange the computation so that amplitudes leading to wrong answers cancel each other out, and amplitudes leading to the right answer reinforce. Then you measure, and the right answer is overwhelmingly likely.

This is why quantum computers are not simply faster at everything. Designing that cancellation requires structure in the problem. For most problems nobody knows how to build the interference pattern, and the quantum machine offers little or nothing.

Factoring and discrete logarithms have exactly the right structure.

03.The structure both problems share

Both problems can be recast as questions about periodicity, and this is the connection that was invisible for twenty years.

Look again at the powers of $3$ modulo $17$ from the previous note:

$$3, \; 9, \; 10, \; 13, \; 5, \; 15, \; 11, \; 16, \; 14, \; 8, \; 7, \; 4, \; 12, \; 2, \; 6, \; 1, \; 3, \; 9, \; 10, \ldots$$

After sixteen steps it returns to $1$ and the whole pattern repeats. The sequence is periodic with period $16$.

Discrete logarithms are a question about where you land inside that repeating cycle. Factoring can also be turned into a period-finding question. Given $n = pq$ and a random $a$, the sequence $a^1, a^2, a^3, \ldots$ modulo $n$ is periodic, and knowing its period $r$ is usually enough to recover the factors: if $r$ is even, then $a^{r/2} - 1$ and $a^{r/2} + 1$ generally share a non-trivial factor with $n$, and one greatest-common-divisor computation finishes the job.

Try it on $n = 143$ with $a = 5$. The powers of $5$ modulo $143$ cycle with period $r = 20$. Then $a^{r/2} = 5^{10} \equiv 12 \pmod{143}$, and

$$\gcd(12 - 1,\; 143) \;=\; \gcd(11, 143) \;=\; 11 .$$

There is the factor. The other is $143/11 = 13$.

So factoring reduces to finding a period. The catch classically is that the period is astronomically large and finding it by walking the sequence takes as long as the exponential search we were trying to avoid.

Period-finding is precisely the task where quantum interference shines. The quantum Fourier transform turns a superposition over a periodic sequence into an interference pattern where amplitudes for anything inconsistent with the true period cancel out. Measure, and the period drops out. That is Shor's algorithm, and it runs in polynomial time in the number of bits.

04.What that means concretely

A fault-tolerant quantum computer of sufficient size would factor a $2048$-bit RSA modulus in hours rather than in the many times the age of the universe that the number field sieve needs. It would solve discrete logarithms, including the elliptic-curve version, just as comfortably.

Both load-bearing problems of deployed public-key cryptography fail at the same moment, to the same machine, running the same algorithm.

The insurance of having two independent problems is worthless, because they were never independent in the way that mattered. They were two faces of periodicity.

05.How close is the machine

Not close, in the sense that matters. Current devices have on the order of hundreds to low thousands of physical qubits, and those qubits are noisy. Quantum states decohere, meaning they leak into their environment and lose the delicate amplitudes the algorithm depends on.

The fix is error correction, which encodes one reliable logical qubit across many noisy physical ones. At today's error rates the ratio is roughly a thousand physical qubits per logical qubit.

Published estimates put a cryptographically relevant attack on $2048$-bit RSA at roughly four to six thousand logical qubits, which means on the order of a million physical qubits. Nobody has built anything within three orders of magnitude of that.

So this is not a next-year problem. It is also not a hypothetical one, because the theory has been settled since 1994 and the engineering curve has been steep for a decade.

06.Harvest now, decrypt later

Here is the part that makes the timeline urgent despite the machine being distant.

Eve does not need a quantum computer today. She needs one eventually. Recording encrypted traffic is cheap, storage is cheap, and patience costs nothing. An adversary can capture your encrypted traffic now, archive it, and decrypt it the day a sufficient machine exists.

This is called harvest now, decrypt later, and it inverts the usual way of thinking about security deadlines. The question is not when quantum computers arrive. The question is how long your data has to stay secret.

Medical records, legal filings, diplomatic cables, intelligence sources, industrial designs, sealed court records. Anything whose confidentiality must survive twenty or thirty years is already exposed, today, by the mere expectation of the machine. It does not matter that the decryption happens in 2045 if the harm of disclosure is just as bad in 2045.

There is also a slower, less dramatic problem. Migrating the world's cryptography takes a very long time. Protocols must be specified, libraries written, hardware built, standards ratified, embedded devices with ten-year deployment lifetimes replaced. Previous cryptographic migrations have taken well over a decade each, and this one is larger.

Between long-lived secrets and a slow migration, the sensible time to start replacing public-key cryptography was some years ago.

07.What survives

It is worth being precise about the damage, because the picture is often overstated.

Public-key cryptography is what breaks. RSA, Diffie-Hellman, elliptic-curve Diffie-Hellman, DSA, ECDSA. Everything built on factoring or discrete logarithms.

Symmetric cryptography largely survives. There is a quantum algorithm relevant here, Grover's, which searches an unstructured space of $N$ items in about $\sqrt{N}$ steps. Against a symmetric key that halves the effective key length, so AES-128 drops to about $64$ bits of security, which is not enough, while AES-256 drops to about $128$ bits, which is fine. The response is to use longer symmetric keys, and that is a parameter change rather than a redesign.

Hash functions are in the same position, and the same doubling response applies.

So the job is not to rebuild cryptography. It is to replace the public-key layer with something whose hardness does not reduce to period-finding. What that replacement is, and how it was chosen, is the next note.