Why Quantum Computers Break RSA | Shor's Algorithm Explained Simply

RSA has been quietly protecting your bank transfers, your messages and your software updates for close to fifty years. Peter Shor sank it on paper in 1994, and a large enough quantum computer will one day sink it in practice.

To understand why, you have to look past the usual one-liner — "factoring large numbers is hard" — and listen for something else entirely: a rhythm hidden inside the encryption itself.

In short:

• RSA's security rests on a cycle that is astronomically expensive to find by trial and error.

• A quantum computer does not search for that cycle. It makes the cycle interfere with itself and reads off its frequency.

• Doubling the key length squares the classical attacker's work. It roughly doubles the quantum attacker's.

How does RSA protect a secret?

For a cryptographer, RSA is close to a cure-all. The algorithm rests on elegant mathematics braiding together arithmetic, number theory and group theory (those words may mean little to you, but anyone lucky enough to have studied them at some point will feel an irrepressible intellectual wriggle). It handles both digital signatures and key transport. It is efficient, and the objects it produces stay modest in size. And — a quality one appreciates enormously in a popular-science article — it is relatively simple to explain.

People usually open by stating that RSA rests on the assumed difficulty of decomposing large numbers into a product of prime factors. That is true, but far too thin to grasp the underlying machinery — which is exactly what a quantum computer exploits.

Two secrets, one public lock

Suppose Alice and Bob want to exchange a secret message. RSA begins by demanding two large prime numbers, call them p and q. Alice obliges: she draws them at random and will not reveal them under any circumstances. They are hers, and hers alone.

She can, however, multiply them together to obtain a third number, N = p × q. If, as we assumed, recovering the prime factors of N is genuinely hard, then Alice has no scruples about publishing N — on the internet, for instance. By hypothesis, a malicious party who gets hold of it will have all the trouble in the world getting back to the two original primes. Excellent.

But we are not done.

Encryption: raising the message to a power

Bob has a message to transmit securely to Alice: "Les sanglots longs des violons de l'automne." You can always turn text into a number — in binary, for example, which is exactly what your computer does to store a Word file (10 KB means the file can be represented with ten thousand bytes, or eighty thousand bits). Call M the message expressed as one large number. Bob has N, Alice has p and q. What now?

This is the moment to fasten your seatbelt. A new number e appears. It is public, and for good reasons it is often chosen to be e = 65537. To encrypt his message, Bob computes M to the power e: M × M × M × … × M, "e times". The result is a very large number, thoroughly incomprehensible to the average mortal. Call it C: the ciphertext, the thing Bob actually sends across the network and that any passing eavesdropper can intercept.

Decryption: going round until M lands back on its feet

The whole question of decryption comes down to recovering M from M^e. It turns out (and we shall elegantly sidestep the proof here) that if you keep multiplying M^e by itself, again and again — computing M^2e, then M^3e, then M^4e, and so on — a providential moment eventually arrives where the whole thing lands back on its feet. There exists a power d such that M^ed = M × M × … × M ("ed times") has a rather interesting property: it is equal to M plus a multiple of N — that same public N from the very beginning. Put differently, M^ed can be written as M + (N × some number).

And there, hope returns. Because subtracting multiples of N is easy (trust me). The conclusion: if you can get this far, expressing a power of M as the sum of M and a multiple of N, you can recover the original M. You have decrypted the message.

In other words, decrypting is a matter of finding the tempo of the round dance that brings M back onto its feet when you multiply it by itself enough times.

The difficulty, obviously, is that groping around for that tempo — that exponent ed — takes a long time. A very long time, particularly when you choose very large numbers: ed sits somewhere around 2^2048, which is to say "more than the number of atoms in the universe", per the customary formula. That represents a staggering quantity of computation, out of reach even for an army of supercomputers.

The shortcut only Alice has

Extremely complicated, granted — except for Alice. Knowing p and q, she can find that tempo, that exponent, very easily, in a handful of operations. There is a deep and elegant reason for this, but it lies beyond the scope of this article.

Splendid. We have a robust, elegant asymmetric encryption scheme, one that has been infusing security into our remote communications for the better part of fifty years.

How does a quantum computer break RSA?

We justified RSA's robustness by the difficulty of finding the right power s of the message M that lets us "land back on our feet" — that expresses M^s as M plus a multiple of N.

And that is precisely the certainty Peter Shor shook in 1994.

If the RSA scheme is vulnerable to Shor's algorithm, and therefore to the quantum computer, it is because it conceals this rhythm, this cycle — and therefore a structure — that quantum computation manages to exploit. With which ingredients?

1. Superposition: is Schrödinger's cat alive or dead?

A quantum state is the way a qubit has been prepared: an electron, a proton, a photon, an atom, or something else. We can interact with these little grains of matter (with lasers, notably) to give them certain characteristics — and in the story that concerns us, we place them in a state that gives one chance in two of reading 0 when measured, and one chance in two of reading 1.

Where a register in a classical processor can only store a single deterministic value, quantum registers have the excellent property of storing something far deeper: a superposition of states, a kind of combination of every state the underlying qubits have been placed in.

Each qubit already stores a superposition of two states, 0 and 1. On measurement, a single state (0 or 1) will be observed, with probability 1/2. But as long as the measurement has not been made, the two states coexist.

This is what we usually depict through the macabre parable of Schrödinger's cat (after the great Austrian physicist and philosopher, a pioneer of quantum mechanics): a cat is shut inside a sealed box with a bowl of poisoned milk. As long as we do not lift the lid — the measurement — is the cat alive or dead? A bit of both, in a sense. Its "alive" and "dead" states are superposed.

Positioning ourselves now at the level of the register: superpose Q qubits (each of which is itself the superposition of the states 0 and 1) and the probability of measuring any number at all between 0 (every qubit measured in its 0 state) and 2^Q^−1 (every qubit measured at 1) is uniform, at 1/2^Q. To measure 1010…1010, for instance, the first qubit must come out as 1 (one chance in two), the second as 0 (one chance in two), the third as 1 (one chance in two), and so on.

Useful, you will say, to build a register that hands you a random number between 0 and 2^Q^−1 when you measure it… Patience. It's coming.

2. Entanglement: the great marriage of the registers

In a second register, we place Q−1 qubits in the state 0 and one qubit in the state 1. Measuring this register invariably yields the value 1 (in binary: Q−1 zeros followed by a single 1).

Now let us measure the state of both registers in their entirety. The global measurement is composed of a random number between 0 and 2^Q^−1 (register 1) and a state 1 (register 2). Put another way: a sort of Cartesian product (we call it a tensor product) of a state of register 1 and a state of register 2. You can separate at will what comes from register 1 (a sum of uniformly distributed states) and what comes from register 2 (a Q-qubit state that always gives 1).

In this global state, the contributions of registers 1 and 2 are independent. They live two happy single lives.

Let us marry them.

Round and round the carousel

By the distributivity of the tensor product between the states of register 1 and the states of register 2, we can also write the global state of the two registers as the superposition of [every possible state of R1, paired with the state 1 carried by R2].

Indeed: I previously had 2^Q suitors in register 1. Taking a photograph of that register handed me one suitor drawn at random from the 2^Q, whom I invariably married to the bride "1" in register 2. I claim this is equivalent to selecting at random one of the 2^Q couples (state 0 ≤ x ≤ 2^Q^−1 of register 1, bride "1" of register 2). It is the couples that are superposed now, not the suitors on one side and the bride on the other.

As everyone knows, marriage alters the character of loving spouses.

That is what is about to happen to the bride in each superposed couple. Rather than being worth 1 with probability 1, we apply one single operation to the entire wedding party, in one gesture. The wife of husband x then takes on a value that depends on x — a function of x.

And here is where the magic of the thing is hiding. You might think that acting on 2^Q couples demands 2^Q computations, one per value of x, which would gain us nothing over a classical computer. Nothing of the sort: the machine does not manipulate the 2^Q values one at a time, it manipulates the Q qubits, once and only once. Because the register is a superposition and the operation is the same for everyone, it applies to every branch simultaneously. One single pass through the circuit, and all 2^Q brides are computed at once.

Why does it work? Because nature is built that way.

Let us continue.

Each husband now has a wife exclusively bound to him. Since the state of each bride is a function of the value of her husband's state, it is no longer possible to go backwards and write the global state of the two registers as an independent product of a register-1 state and a register-2 state. The two states are intrinsically linked. Or rather, they are entangled.

The function of x carried by each bride is not left to chance. It is equal to f(x) = C^x (mod N), where C = M^e is the intercepted ciphertext — well, well, we recognise the shape of the "supposedly hard" problem from the previous section, with the message M encrypted by exponentiation. The "(mod N)" simply indicates that we ignore multiples of N when computing f(x): if C^x₁ and C^x₂ differ by a multiple of N, we consider f(x₁) and f(x₂) to be equal.

Quantum polygamy

A useful question: is every bride different? Or are there wives bound to several different husbands?

Imagine we find a number r such that C^r = 1 (mod N) — we know one exists. Then, if x is some husband in register 1 married to his wife f(x), we have f(x+r) = C^x+r = C^x · C^r = C^x · 1 = C^x (mod N) = f(x). So f(x) is also the wife of x+r — and, for that matter, of every husband of the form x + kr, with k a whole number. Let us call this the polygamy property, in which the bride reigns supreme.

An immediate and rather startling consequence: any measurement of register 2 affects the measurement of register 1. If we measure a certain bride y = f(x) in register 2, we will necessarily measure the superposition of the states of the husbands x such that y = f(x). That is, husbands of the form x, x+r, x+2r, x+3r…

You might believe we have reached the end of the reasoning. After all, finding that wretched r means getting our hands on the system's secret rhythm. And that rhythm opens exactly the same door as the shortcut Alice drew from p and q: remember d, the magic exponent from the first part, the one a classical attacker would need billions of years to guess? Once r is known, d follows in the blink of an eye, and with it the message M is recovered. Never mind the exact arithmetic — what matters is that r plays the role of Alice's prime numbers.

But we do not have access to r yet. We might be tempted to measure register 1 right now — except we would then obtain some value x+kr, with x and k both unknown. The hunt for r is still open.

3. Wave-particle duality: "and yet it vibrates"

Were you told that qubits contain a particle of matter? You were lied to. Half-lied to, at any rate.

The beauty of the thing is that we cannot decide which of the two models, wave or particle, better describes elementary matter. We call this wave-particle duality.

Which means we get to pick whichever representation suits us.

Making the basin vibrate

Picture ripples on the surface of water. We send one ripple at t = x, another at t = x+r, another at t = x+2r, and so on: we obtain a set of waves spaced r apart.

From the other side of the basin, we send further ripples spaced s = 1 apart, then 2, then 3, and so on up to N. Try the experiment and two scenarios will unfold in front of you:

• s differs from r: your basin becomes a bedlam of little waves breaking over one another.

• s equals r: the troughs of the ripples sent from the left line up with the troughs of those sent from the right, digging deeper troughs still; and their crests coincide too, raising higher crests.

What we have just described is the phenomenon of constructive interference. When you play an A on the guitar and hum an A at the same time, the sound seems to swell in volume — because the sound ripples of the guitar and of the voice add and subtract in the right places, making the vibration more intense.

The rhythm recovered

This is roughly what happens when we go looking for r in the problem that concerns us: we attempt to recover the "vibration" frequency of our system through interference. (In the textbooks, this step goes by the name of the quantum Fourier transform.)

r is obtained. The message M is decrypted, via the little exponent computation described earlier.

Right — this is the moment where you have to take the author's word for it: the whole set of computations that recovers r, that hidden period, is ridiculously small compared with the titanic effort of computing every power of M in the classical case.

Better still, everything comes down to the manner of the attack. The classical computer has no rhythm to exploit. It is condemned to try the powers one by one, to rummage through a haystack whose size doubles with every bit added to the key. Doubling the key length (2048 → 4096 bits) therefore squares that haystack, multiplies it by itself: the work explodes. The quantum computer rummages through nothing. It listens directly to the rhythm r through interference, and the cost of that listening depends only on the number of digits to be manipulated. Twice as many bits, twice as many qubits, and that is about it.

Frequently asked questions

Does Shor's algorithm actually factor N? Not directly. The quantum step is period finding — recovering the r above. Factoring N, and recovering the message, both fall out of r with a bit of classical arithmetic. The factoring headline is a consequence, not the mechanism.

Can today's quantum computers break RSA-2048? No. Breaking a 2048-bit key calls for thousands of error-corrected logical qubits running very deep circuits, while the best machines currently field only dozens of logical ones. What has been moving fast is the estimate, not the hardware: a 2025 Google Quantum AI analysis brought the requirement down to under a million noisy physical qubits, roughly twenty times lower than the 2019 figure, and 2026 preprints on alternative error-correcting architectures argue for less still. The threshold keeps falling before a single new qubit is built.

Does a longer key protect me? It buys time, not safety. Classical attack cost grows exponentially with key length; quantum cost grows roughly linearly. That is the whole asymmetry of this article in one sentence.

Is RSA the only casualty? No. Diffie-Hellman and elliptic-curve cryptography fall to the same attack, for the same reason: they hide a periodic structure. Elliptic curves will likely fall first, since their stronger classical security led people to adopt much shorter keys — and Shor's algorithm mostly cares about key size. Symmetric ciphers such as AES are far less exposed.

What replaces RSA? NIST standardised its first post-quantum algorithms in August 2024: ML-KEM (FIPS 203) for key exchange, ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) for signatures, with HQC added as a backup in March 2025. RSA and ECC are slated for deprecation around 2030 and disallowance by 2035.

Why migrate now if no machine exists? Because of harvest now, decrypt later: an adversary can record encrypted traffic today and decrypt it the day a capable machine arrives. Any secret that must stay secret for a decade is already exposed.

Disclaimer

Certain difficulties have been knowingly sidestepped throughout this article. Purists will certainly find a few points of detail to quibble with, and I beg their clemency in the name of popularisation.