How Shor's algorithm actually breaks RSA

Every post-quantum pitch, ours included, gets round to the same line sooner or later: a big enough quantum computer will break RSA. Ask how and you'll usually be told that a qubit can be 0 and 1 at the same time, so a quantum computer tries every answer at once.

That doesn't get you very far. If a machine tried every answer at once and then showed you one of them at random, you'd be no better off than if you'd guessed. A quantum computer doesn't hand over the answer in one go, either. It loads the dice so that the right answer comes up much more often than it should, and then you roll them a few times. How the dice get loaded is the interesting bit, and you can follow it without any physics.

So we're going to build a tiny RSA key and then break it with Shor's algorithm, by hand, on a number small enough to fit on a clock face: 15.

How RSA works

RSA does its arithmetic on a clock. An ordinary clock only keeps the hour after it passes 12, so three hours after 11 o'clock is 2. RSA does the same thing with a much bigger clock: it keeps only the remainder after dividing by some number, N. On a clock of 15, 17 is 2 and 49 is 4.

To make a key, you pick two secret primes and multiply them together. The result is N, the size of the clock. You also choose a public power, and publish it along with N. Real keys use primes hundreds of digits long. We'll use 3 and 5, so our clock is 15, and we'll pick 11 as the public power.

To send you a message, someone writes it as a number, say 2, and raises it to your public power on your clock. 2¹¹ is 2048, which is 8 on a clock of 15, so they send you 8. To read it, you raise 8 to your private power, which is 3. 8³ is 512, which is 2 on the clock, and the message is back.

Why does 3 undo 11? On a clock of 15, raising a number to the 4th power brings it back to 1. (A few numbers share a factor with 15 and behave a little differently, but they still come out right in the end.) Raising the message to the 11th and then the 3rd is the same as raising it to the 33rd, and 33 is eight lots of 4 plus one. Each lot of 4 lands back on 1, and the one left over leaves you with the message.

The 4 comes straight from the primes. It's the smallest number that both 3 − 1 and 5 − 1 divide into evenly, and we'll see why further down. If you know the primes, you can work out the 4, and from the 4 the private power, in moments. If all you know is 15 and 11, you're stuck.

So swap sides for a moment. You're an attacker, and all you have is the public key: 15 and 11. Find the two primes and you can rebuild the private key exactly the way its owner did. Breaking RSA comes down to one question: given N, what are its two factors?

For a 2,048-bit key, N is more than 600 digits long, and no classical method would factor it in any useful amount of time. Shor's algorithm finds a way round that.

What we're looking for

We'll attack our toy key and keep track of every number as we go. Here's what's on the table at the start:

The route is: find the period, then turn the period into the two primes. First, what the period is.

Factoring is secretly about rhythm

In 1994, Peter Shor showed that you can swap factoring for a different problem: working out how often a sequence repeats.

Here's the sequence. Take the starting number, 7, and raise it to higher and higher powers on our clock of 15.

7⁰ is 1. 7¹ is 7. 7² is 49, which is three lots of 15 with 4 left over, so 4. Then 13, then 1 again. From there it goes round and round: 1, 7, 4, 13, 1, 7, 4, 13.

You never need the big numbers. Each power is the last one times 7, and on a clock only the remainder matters, so you can multiply the remainder instead. 7³ is 7² × 7, and 7² is 4 on the clock, so 7³ is 4 × 7 = 28, which is 13. Work it out the long way and you get the same thing: 7³ is 343, which is 22 lots of 15 with 13 left over.

It always comes back round, whatever N is and whichever starting number you pick, as long as it shares no factor with N. The number of steps it takes to get back to 1 is called the period. For 7 on a clock of 15, it's 4, the first unknown in our table.

Why the period gives away the primes

So we have a rhythm. Why should a rhythm have anything to do with the primes?

Because a clock of 15 is really two smaller clocks stuck together: a clock of 3 and a clock of 5. Every number on the big clock is also a position on each small one. 7 is two 3s with 1 left over, so it's 1 on the clock of 3, and it's 2 on the clock of 5. Multiply on the big clock and both small hands move with it.

Clocks whose size is a prime have a useful habit, which Fermat spotted in 1640. Start anywhere except 0, keep multiplying by the same number, and you're back on 1 within one step fewer than the size of the clock. So the clock of 3 always comes back round within 2 steps, and the clock of 5 within 4.

The big clock is back on 1 only when both small clocks are on 1 at the same time, and that's where the period comes from. For 7, the clock of 3 sits on 1 the whole way and the clock of 5 goes 2, 4, 3, 1, so they line up after 4 steps. It's also where the 4 in our RSA key came from. The primes set how the small clocks cycle, every 2 steps and every 4, and both are back at the start every 4 steps.

Now stop halfway through the period, at 7², which is 49. On the clock of 3, 49 is on 1. On the clock of 5, it's on 4, one step short of a full turn. It has to be one or the other: on a prime clock, the only places that land on 1 when you square them are 1 itself and the spot one short of a full turn.

Take one away from 49 and you get 48. That moves the clock of 3 from 1 to 0, so 48 is a multiple of 3. Add one instead and you get 50, which moves the clock of 5 round to 0, so 50 is a multiple of 5. Each neighbour of 49 catches one prime.

To pull the primes out, ask what each neighbour has in common with 15. Euclid's method for the greatest common divisor does it in two lines each:

• 48 and 15: 48 is three 15s with 3 left over, and 3 goes into 15 exactly. They share 3.
• 50 and 15: 50 is three 15s with 5 left over, and 5 goes into 15 exactly. They share 5.

With a 600-digit N the neighbours are 600-digit numbers too, and nobody could spot their factors by eye. Euclid's method doesn't care. It takes at most about five steps per digit, a few thousand for a real key, which a laptop gets through in an instant.

Sometimes the trick doesn't work. If the period is odd, there's no halfway point. If both small clocks happen to sit one short of a full turn at the halfway point, both primes land in the same neighbour. Either way you pick a different starting number and go again. For an RSA modulus that happens at most half the time, so you won't be trying for long.

So why not just count?

If all you need is the period, why not walk round the clock until you get back to 1? We just did exactly that, and for 15 it took four steps. For a 2,048-bit N, the period is typically a number hundreds of digits long. You'd still be counting when the sun burns out.

Working out any one power is quick, even for enormous numbers. Finding where the sequence repeats, without walking the whole thing, is the hard part. So from here on, let's pretend we never walked the clock. The quantum computer knows that N is 15 and the starting number is 7, and that's all. Its job is to find the period, the 4, without counting.

Here's how it does that, in five moves. We'll go through them one at a time.

• 1. Set up an input register that could read any number from 0 to 31, all equally likely.
• 2. Run the oracle once, which writes 7ˣ next to every x.
• 3. Read the output. That leaves the input holding a comb: the values of x that gave that output, one period apart, starting somewhere random.
• 4. Run the Fourier transform on the input. Teeth one period apart become peaks 32 ÷ period apart, and the random start drops out.
• 5. Read the input, write the reading as a fraction of 32, and the bottom of the fraction gives you the period.

The register has 32 slots, which is 5 qubits. That's enough to see everything without drowning in numbers. The first piece is the oracle.

The oracle is just arithmetic

Despite the name, there's nothing mystical about the oracle. It's a circuit that takes a number x and works out 7ˣ on our clock of 15. It's the same sum we did by hand, built out of gates.

It works the way you'd do it on paper. Write x in binary. Each bit switches one multiplier on or off: the 1s bit multiplies by 7, the 2s bit by 7², the 4s bit by 7⁴, and so on up to the 16s bit. Those constants get worked out in advance on an ordinary computer, by squaring, and on our clock they come to 7, 4, 1, 1 and 1. Multiply together the ones that are switched on, and you have 7ˣ.

Take x = 6, which is 00110 in binary. The 2s and 4s bits are on, so the oracle starts from 1, multiplies by 4, then by 1, and out comes 4. You can check it on the clock: six steps on from 1 lands on 4.

Building it for a quantum computer adds one rule: every step has to be reversible, so nothing can be thrown away. The oracle leaves its input alone and writes its answer into a second register next to it. That pairing is what the next step relies on.

For RSA-2048 the oracle is enormous, and it accounts for nearly all the work in the estimates further down, but it's still just arithmetic.

Run it once, on everything

This is where the quantum computer earns its keep, and where the usual explanation goes wrong.

First, what a quantum register holds. An ordinary 5-bit register holds one number from 0 to 31. A quantum one holds a hand for every number it could show: an arrow whose length says how likely you are to read that number, and whose direction we'll need later. Reading the register picks one number, longer hands winning more often, and every other hand is gone. You get one reading per run.

We start with 32 equal hands, all pointing the same way, so every x from 0 to 31 is equally likely. Then we run the oracle once. Every x now sits next to its own 7ˣ.

If we read both registers at this point, we'd get one row of that table, picked at random: one x and its answer, which a calculator could have told us. That's why the “every answer at once” story stops short.

What we do instead is read only the output register. Say it shows 4. Every hand whose x doesn't give 4 is gone, and the ones left, at 2, 6, 10, 14, 18, 22, 26 and 30, share all the chance between them. (Strictly speaking, you don't need to read the output at all, and the maths comes out the same. Reading it just makes the picture easier to see.)

Look at those numbers. They're 4 apart, and 4 is the period we're hunting for. It's sitting in the register as a comb, with a tooth every 4 places.

We still can't just read it off. Reading the input register now would give us one tooth at random: 2, or 6, or any of the others up to 30. One tooth tells you nothing about the spacing. And where the comb starts depends on which output we happened to see, so the position of any one tooth is noise. We want the spacing and nothing else.

Hearing the rhythm

The last quantum step, the quantum Fourier transform, takes care of that. A Fourier transform is the maths inside a guitar tuner: it tells you the pitch of a note no matter when you started playing it. Give it our comb and it tells you how often the teeth repeat, no matter where the comb starts.

How it does that comes down to another clock.

Hands on a clock

Draw a circle and mark 32 evenly spaced directions round it, like a clock with 32 hours. Mathematicians call these the 32nd roots of unity. For our purposes they're just the places a hand can point. Most of the gates inside the transform do nothing more exotic than turn hands round this clock.

After the transform, every possible reading k, from 0 to 31, gets a new hand. k is just a number you might read at the end, and it isn't the period. To build k's hand, the transform takes every tooth of the comb, turns its hand x × k thirty-seconds of the way round, and adds them all up nose to tail. The longer the total, the more likely you are to read k. If it comes to nothing, you never will.

Try k = 1. The teeth at 2, 6, 10 and so on up to 30 get hands turned 2, 6, 10 … 30 thirty-seconds of the way round: eight hands spread evenly round the circle, an eighth of a turn apart. Nose to tail, they come straight back to the start. The total is zero.

Try k = 8. Each tooth's hand turns x × 8 thirty-seconds, which for every tooth works out to some whole number of turns plus a half. All eight point straight down and add up to the longest total there is.

Why only some readings? Teeth 4 apart get hands k × 4 thirty-seconds apart, which is k eighths of a turn. When k is a multiple of 8, that's a whole number of turns, so the hands line up. Otherwise they spread round the circle, or pair off opposite each other, and cancel. The only readings left are 0, 8, 16 and 24, the multiples of 32 ÷ 4.

So a tooth every 4 places becomes a peak every 32 ÷ 4 = 8 places. The period is still in there, upside down: the more often the teeth repeat, the further apart the peaks.

What about the starting point? Shift the comb along by one and every hand turns by the same extra amount. The total turns with them but keeps its length, and reading the register only sees the length. So the transform throws the starting point away and keeps the spacing.

So the quantum part of Shor's algorithm is interference: hands lined up so the wrong answers cancel and the right ones survive. What survives is a set of odds.

Reading the answer, one roll at a time

Now we read the input register, which is one roll of those loaded dice. We get 0, 8, 16 or 24, each a quarter of the time.

To turn a reading into the period, write it as a fraction of 32. The peaks sit a whole number of 32 ÷ 4 steps along, so the fraction always comes out as some whole number over the period: 8 is ¼ of the way, 16 is ½ and 24 is ¾. Cut the fraction down as far as it goes, and the bottom is the period, unless the top and the period had a factor in common.

• Read 8: 8/32 is ¼, so the bottom is 4. Check: 7⁴ is 1 on the clock. That's the period, and the two small clocks take it from there to 3 × 5.
• Read 24: 24/32 is ¾. The same 4.
• Read 16: 16/32 is ½, which suggests 2. Check: 7² is 4, so 2 is wrong. The fraction was really ²⁄₄, and cutting it down hid the 4.
• Read 0: 0/32 tells you nothing. Run it again.

Notice that at no point did the quantum computer tell us the answer. Every run ends with one random reading. What the oracle and the transform did was change the odds. Without the transform, every position from 0 to 31 is as likely as any other. With it, all the chance piles up on the four positions that lead to the period. Run it a few times, check each reading with ordinary arithmetic, and you'll have the answer soon enough. Half the time the first run does it.

We made life easy for ourselves by using a register of 32, which the period divides exactly, so the wrong positions can't come up at all. With a real N that almost never happens. The peaks smear out a little, and now and then a run lands somewhere useless. The right answers are just the most likely ones. It doesn't matter much: a bad reading fails a cheap check and you roll again. A classical method called continued fractions turns each slightly-off fraction back into a candidate period. A real run also uses an input register with about twice as many bits as N, which keeps the peaks sharp, so a handful of runs will do.

A handful of runs, against a count that would outlast the sun. That's the speed-up.

The whole algorithm

Put together, Shor's algorithm is mostly an ordinary program with one quantum subroutine in the middle:

• Classical: pick a starting number that shares no factor with N.
• Quantum: run the oracle once over every input, read the output register, then apply the Fourier transform to the input register.
• Quantum: read the input register to get a fraction.
• Classical: turn the fraction into the period, find the halfway point, and use Euclid's method on its two neighbours to get the factors. If it didn't work, start again.

Nothing in that list depends on 15 being small. The same steps factor a 2,048-bit N. The registers get longer and the oracle gets much, much bigger.

How big is big enough?

So far the numbers factored with Shor's algorithm on real hardware are tiny, like 15, and even those runs took shortcuts that only work when you already know the answer. Breaking real keys needs a far bigger machine than anyone has built, but the estimates of how big keep coming down:

• 2019: Craig Gidney and Martin Ekerå put RSA-2048 at about 20 million qubits and eight hours.
• May 2025: Gidney, at Google Quantum AI, brought it under a million qubits, taking a little under a week.
• February 2026: the Pinnacle architecture claimed under 100,000 qubits, using a different kind of error correction.
• March 2026: Cain and colleagues argued that Shor's algorithm could run at cryptographic scale on as few as 10,000 atomic qubits, if you can wait longer for the result.

These assume different hardware, so they don't compare neatly, and every one of them is a design for a machine that doesn't exist yet. But they're all designs for the algorithm we just ran on 15, and the numbers keep coming down.

The same approach breaks elliptic-curve cryptography too, which covers the X25519 and ECDSA keys behind most VPNs, TLS connections and code signing. The rhythm is hidden in a different kind of clock, and it may well be the easier target: the March 2026 estimate puts a 256-bit curve at a few days on 26,000 qubits.

You also don't have to wait for that machine to be at risk. Traffic recorded today can be decrypted on the day one exists. If your data has to stay secret for ten years, its clock started the moment you sent it.

What doesn't have a rhythm

Shor's algorithm works because RSA and elliptic curves hide a period, a sequence that comes back round to where it started. ML-KEM and ML-DSA, two of the post-quantum standards NIST published in 2024, are built on a different kind of hard problem, based on lattices: grids of points in hundreds of dimensions, with deliberate noise mixed in. There's no period to find, and nobody knows a quantum algorithm that does to lattices what Shor's does to RSA.

Symmetric ciphers like AES aren't affected by Shor's algorithm at all. The best known quantum attack on them, Grover's algorithm, at most halves their effective key length, which is why 256-bit keys are the long-term choice.

VeilNet uses both. ML-KEM-1024 agrees the keys, ML-DSA-87 signs every identity and credential, and AES-256-GCM encrypts the traffic itself. None of them has a rhythm for Shor's algorithm to find.

See it for yourself

Read how the pieces fit together in the architecture docs, try VeilNet Conflux on your own machines, or book a demo and we'll walk you through it. If you have questions about any of this, from the maths to your migration plan, write to us at sovereign@veilnet.net.