The Question Behind the Question

It started with a clock.

Not a special clock. The one on your wall. Twelve numbers, and a rule so familiar you have never thought of it as a rule: when the hour hand passes 12, it wraps back to 1. Nine o’clock plus five hours is not fourteen o’clock. It is two o’clock. The clock does not care how many total hours have passed. It only cares about the remainder.

Mathematicians call this modular arithmetic, which means arithmetic that wraps around a fixed number the way a clock wraps around 12. It is the kind of thing that looks like a curiosity, a party trick for number theorists. It is also the crack in the foundation of RSA. Because in 1994, a mathematician named Peter Shor noticed that the problem protecting most of the world’s encrypted traffic, the problem I wrote about last week, is secretly a question about clocks. And questions about clocks have a property that questions about factoring do not.

They have a rhythm. And rhythms can be heard.

Where we left off

I am the person who needed to understand what the cryptographer’s work means for the world I live in, so let me restate the situation in plain terms. In the last post, I walked through why RSA and elliptic curve cryptography are safe from classical computers. The security of RSA rests on a single fact: multiplying two large prime numbers together is easy, but starting from the product and recovering the two primes is brutally hard. Every classical factoring method we know, even the clever ones, chokes when the numbers get big enough. That is why your bank can publish its public key on the open internet and sleep fine.

And in the post before that, I made the case that a quantum computer is not a faster version of your laptop. It does not try answers more quickly. It plays a different game entirely, one where wrong answers can be made to cancel each other out and right answers can be made to reinforce.

Here is the problem those two posts leave us with. Cancellation is a wonderful trick, but it only works if the problem has some structure for the cancellation to grab onto. You cannot point a quantum computer at a pile of random possibilities and ask the wrong ones to politely eliminate themselves. There has to be a pattern.

Factoring, on its face, has no pattern. A 2048-bit RSA number is just a wall. There is no rhythm in a wall.

Shor’s insight, the reason his name is on the algorithm, was not a quantum insight at all. It was a classical, mathematical insight. He found the pattern. He showed that hiding inside every factoring problem is a completely different problem, and that different problem repeats like a heartbeat.

The trick: stop asking about factors

Take the number you want to factor and call it N. Now pick some smaller number, more or less at random. Call it a. Then start computing the powers of a, but on a clock with N positions instead of 12. In other words, compute a, then a squared, then a cubed, and so on, but every time you pass N, wrap around and keep only the remainder.

Let me make that concrete with a number small enough to do by hand. Say N is 15 and we pick a = 2. Here are the powers of 2 on a 15-hour clock:

• 2 to the 1st power is 2
• 2 squared is 4
• 2 cubed is 8
• 2 to the 4th is 16, which wraps around to 1
• 2 to the 5th is 32, which wraps around to 2
• 2 to the 6th wraps around to 4
• 2 to the 7th wraps around to 8
• 2 to the 8th wraps around to 1

Look at the outputs: 2, 4, 8, 1, 2, 4, 8, 1. The sequence repeats. It cycles through exactly four values and then starts over, forever.

That cycle length has a name. It is called the period, meaning the number of steps a repeating sequence takes before it starts over. Here the period is 4. And this is not a quirk of the numbers I picked. It is guaranteed. For any N and almost any a, the powers of a on an N-hour clock will eventually loop back to 1 and repeat. The sequence always has a rhythm. The only question is how long the rhythm is.

Finding that number is called period-finding, and it is the question behind the question. Because here is the part that still strikes me as slightly unfair to classical computers.

If you know the period, the factors fall out

Watch what happens with our example. The period was 4. Take a raised to half the period. That is 2 squared, which is 4. Now compute two numbers: one less than that, and one more than that. You get 3 and 5.

Those are the factors of 15.

That is not a coincidence, and the reason is one step of algebra I will describe in words rather than symbols. Saying the sequence returns to 1 after r steps is the same as saying that a to the r, minus 1, is divisible by N. And a classic identity from school algebra says that “something squared minus one” splits into “something minus one” times “something plus one.” So N divides evenly into the product of those two smaller pieces. Since N cannot usually fit entirely inside either piece alone, its prime factors have to split up, some landing in one piece and some in the other. Run a greatest-common-divisor calculation between N and each piece, which is an operation so cheap that computers have done it instantly since the 1970s, and the factors surface.

There are caveats, and I want to be honest about them because the details matter. The period needs to be even for the “half the period” step to make sense, and occasionally the algebra collapses in a way that tells you nothing. When that happens, you throw away your choice of a, pick a new one, and try again. The math says a random a works often enough that a handful of tries is essentially always sufficient. This is not a lottery. It is a procedure with a retry button.

So here is the new shape of the world after Shor’s classical insight, before any quantum hardware enters the picture. Nobody needs to factor N directly. They need to find the period of one repeating sequence. Factoring has been converted, exactly and provably, into period-finding.

Your classical instinct is now asking the obvious question: so what? And your classical instinct is right to ask.

Why this does not help a classical computer at all

Because for a real RSA number, the sequence is obscene. The period of that repeating pattern is not 4. It can be a number comparable in size to N itself, which for RSA-2048 means a number with hundreds of digits. A classical computer finds a period the only way it can: compute the sequence, step by step, and watch for the repeat. Walking a sequence whose period has 600 digits is the same astronomical wall we started with. We have not shrunk the problem. We have only changed its shape.

But the shape is everything.

Think back to the bombe. Turing did not defeat Enigma by trying every rotor setting and reading the output, because there was no time in the war, or in several universes’ worth of wars, to do that. He defeated it by finding structure: a known scrap of plaintext, and the machine’s own strange rule that no letter could encrypt to itself. The structure let whole continents of wrong answers be discarded without ever being visited. You do not defeat an astronomical number by counting through it. You defeat it by exploiting structure.

A wall has no structure to exploit. A rhythm does.

A period is not a property of any single step in the sequence. You cannot look at one value, or a thousand values, and read the period off of them. The period is a global property, a fact about the whole sequence at once. And a global property of a vast space is exactly the kind of thing a classical computer is worst at, because a classical computer can only ever stand in one place in that space at a time.

It is also exactly the kind of thing a quantum computer was born for.

The opera singer

Here is the analogy I want you to carry into the next post, because the next post is the payoff of this entire series.

An opera singer can shatter a wine glass with her voice. She does not do it with volume, and she certainly does not do it by singing every note on the piano one at a time, tapping the glass after each note to check for cracks. She does it by finding the one frequency the glass already wants to vibrate at. When she sings that note, the glass itself responds. Every wave of sound arrives in step with the glass’s own motion, each push reinforcing the last, until the energy piles up and the glass fails. Sing any other note and the pushes arrive out of step, canceling their own effort. The glass does not budge.

The glass is not being searched. The glass is being asked, all at once, what its natural rhythm is. And the glass cannot help but answer.

Now recall the machinery from two posts ago. A quantum computer can hold a superposition, which means it can load the entire repeating sequence, every step of it, into its qubits at once. Qubit is short for quantum bit, and the “not knowing versus not being” distinction from that post applies here with full force: the machine has not secretly picked one step of the sequence that we simply have not looked at yet. The whole sequence is genuinely present, the way the water of a pond is present across the entire pond and not hiding at one point on it.

What Shor needed was the opera singer’s move. A way to make that loaded sequence ring at its own natural frequency. A way to make every wrong guess about the period cancel itself out, pushes arriving out of step, while the one right answer reinforces, wave after wave after wave, until it is the only thing left standing when you measure.

That move exists. It is called the Quantum Fourier Transform (QFT), and it is the single most important idea in this entire story. It is also, I promise, less frightening than its name. You have been using a Fourier transform your whole life. Your ears do it every time you pick a single voice out of a crowded room.

That is the next post.

Where this leaves us

Let me pin down what we have and have not established, because I do not want the excitement of the trick to outrun the truth of it.

We have established that factoring, the wall that protects RSA, is mathematically equivalent to period-finding, and that the conversion between them is cheap and classical. No quantum hardware was involved in anything I described today. Shor’s bridge is pure mathematics, and it was in some sense sitting there waiting to be noticed, the way the flaw in Enigma’s design was sitting there waiting for Turing.

We have not yet established that a quantum computer can actually find the period. That claim carries the whole weight of the threat to RSA, and it deserves its own post rather than a hand wave at the end of this one.

But notice what has already changed. Before Shor, breaking RSA meant scaling a featureless wall. After Shor, breaking RSA means hearing a rhythm. Those are different problems in kind, not in degree. And if the last seventy years of this story have taught us anything, from the bombe forward, it is that problems with structure do not stay hard forever. Someone eventually builds the machine that listens.