Image: Dori, Wikimedia Commons, CC BY 2.5What Shor's algorithm does to RSA, and when
When your browser connects to a bank, the two sides agree on a secret key by exchanging numbers in public, and the exchange is safe because turning those public numbers back into the secret requires solving a mathematical problem that no known computer can solve in less than the age of the universe. For the RSA system, invented in 1977 and still in wide use, the problem is factoring: given a number with 617 decimal digits that is the product of two primes, find the primes. The largest such number factored by classical means, in 2020, had 250 digits and took about 2,700 years of processor time. In 1994 Peter Shor, then at Bell Laboratories, showed that a quantum computer could factor the 617-digit number in hours.
Factoring as period finding
Shor's algorithm does not search for factors. It uses a piece of number theory known since Euler. Choose any number \(a\) smaller than the number \(N\) you want to factor and compute the sequence \(a, a^2, a^3, \ldots\), each reduced to its remainder on division by \(N\). The sequence repeats with some period \(r\). With a little luck, which can be arranged by trying a few values of \(a\), knowing \(r\) gives a factor of \(N\) in two lines of arithmetic: the number \(a^{r/2} - 1\) shares a factor with \(N\), and the greatest common divisor, which Euclid's algorithm finds in an instant, reveals it.
Finding the period classically is as hard as factoring, because the sequence has to be followed for up to \(N\) steps before it repeats. A quantum computer finds it differently. It prepares a register of qubits in a superposition of all numbers from 0 to a large bound, computes \(a^x\) modulo \(N\) for all of them at once into a second register, and measures the second register. The first register is left in a superposition of exactly those \(x\) that gave the measured value, which are spaced \(r\) apart. A quantum Fourier transform, which is the quantum version of the operation that turns a sound wave into its spectrum, converts that regular spacing into a sharp peak at a multiple of \(1/r\), and measuring the register reads off \(r\) with high probability. The whole procedure needs a number of operations that grows as a modest power of the number of digits of \(N\), where the best classical method grows faster than any power. Shor's paper is readable with the mathematics of a first university course.
Why it is not a general speed-up
The algorithm works because factoring has a hidden periodic structure that the Fourier transform can find. Most problems have no such structure, and for them quantum computers offer much less. Searching an unsorted list of a million items takes a classical computer about a million steps and a quantum computer about a thousand, by Grover's algorithm of 1996, which is a real gain and nothing like the exponential gain for factoring. Problems such as breaking a well-designed symmetric cipher like AES are in this second class. Doubling the key length restores the margin, and the ciphers that protect data once a key has been agreed are not in danger.
What is in danger is the key agreement itself. RSA and the elliptic-curve methods that have largely replaced it both rest on problems with the periodic structure Shor's algorithm exploits. A quantum computer that breaks one breaks the other.
How large a machine
Here the numbers have moved. Running Shor's algorithm on a 2048-bit RSA number needs a few thousand logical qubits that perform billions of operations without error. Physical qubits make errors at a rate of about one in a thousand, so each logical qubit has to be encoded in many physical ones that correct each other, and the overhead is large. An estimate by Craig Gidney and Martin EkerÄ in 2021 put the requirement at about 20 million physical qubits running for eight hours. In 2025 Gidney published a revised estimate, using better error-correcting codes and a cleverer arithmetic, of fewer than one million physical qubits running for less than a week.
The largest quantum processors in 2025 had about a thousand physical qubits, and none of them could yet run a single logical qubit for a week. A million qubits with the required error rates is a different kind of machine from anything that exists, and most researchers in the field put it more than a decade away. Nobody puts it at never. The trend in both the hardware and the estimates has been in one direction.
Harvest now, decrypt later
A decade is not long for secrets. A message intercepted and stored today, encrypted with RSA, can be read by whoever holds the recording once the machine exists. Government communications, medical records, and industrial designs often need to stay secret for longer than that, and security agencies have said openly that they assume their adversaries are recording encrypted traffic now for exactly this purpose. The threat to such data is present, whatever the date of the first large quantum computer.
What is being done
The response is to replace the vulnerable methods with ones based on problems that have no known quantum shortcut. After an eight-year public competition, the United States standards institute NIST published its first three post-quantum standards on 13 August 2024: one for key agreement, based on lattices, and two for digital signatures. Major browsers and messaging apps had begun switching their key exchanges to hybrid schemes, combining a classical method with a lattice-based one, in 2023 and 2024, so that a connection is secure as long as either method holds. The migration of the world's software is expected to take most of a decade, which is roughly the time available.
None of the new standards is proven secure; no cipher is. They rest on problems that have resisted both classical and quantum attack for decades, and one of the finalists in the competition was broken in 2022 by a classical computer in an hour, which is why several methods were standardized rather than one.
What to take from it
Shor's algorithm is the clearest case of a quantum computer doing something useful that a classical one cannot, and it is the reason governments and companies fund the field. The machine that runs it on real keys does not exist. The cryptography that resists it does, and is being deployed. Both facts are true at once.
In the Quantum Mechanics Masterclass, Unit 15 presents the period-finding reduction above, the quantum Fourier transform on a small number of qubits, and Grover's algorithm with its square-root count, and Unit 14 presents quantum key distribution, which is a different answer to the same threat, based on physics rather than mathematics. The error correction that stands between a thousand qubits and a million is the subject of Unit 16.


