What is Shor's Algorithm? Explained Simply

The Quiet Crisis Hiding in Your Browser Bar

Right now, as you read this sentence, your browser is almost certainly protecting a connection using RSA encryption. Your bank login, your email, your credit card number mid-checkout—all of it rests on one stubborn mathematical fact: multiplying two enormous prime numbers together is trivially easy, but pulling them back apart is brutally, almost impossibly hard.

That asymmetry is the lock. And in 1994, a mathematician named Peter Shor found the key.

He didn't build a quantum computer. He didn't even need one to exist yet. He simply proved, on paper, that if one existed, it could factor those enormous numbers in polynomial time—turning a task that would take classical supercomputers longer than the age of the universe into something a quantum machine could finish over a cup of coffee.

The cryptography world collectively held its breath.

The Classical Dead End and RSA's Secret Shield

Here's the game RSA plays. Pick two massive prime numbers—say, each around 300 digits long. Multiply them. You get a number N with roughly 600 digits. Publishing N is fine. Keeping the two original primes secret is the whole security model.

Why? Because reversing the multiplication—factoring N back into p and q—is where classical computation hits a wall.

Think of it this way: mixing two paint colors takes a second. Separating them back into the exact original pigments? Effectively impossible without knowing what went in.

The best classical factoring algorithm we have is the General Number Field Sieve (GNFS). Its time complexity grows sub-exponentially with the size of N, which sounds better than exponential but is still catastrophically slow for 2048-bit keys. We're talking billions of years on the fastest hardware available today. The number isn't just large—it's large in a way that makes brute-force search structurally hopeless.

So RSA sat comfortably for decades. Until Shor asked a deceptively simple question: what if we stop trying to factor directly?

Shor's Brilliant Pivot

This is the conceptual leap that makes Shor's algorithm a masterpiece. He didn't attack factoring head-on. He reframed it.

Instead of asking "what are the factors of N?", Shor asked: "what is the period of a certain repeating pattern?"

Here's how. Pick a random number x that shares no common factor with N. Now compute the sequence:

x¹ mod N, x² mod N, x³ mod N, x⁴ mod N, …

The "mod N" part means you take the remainder after dividing by N—exactly like a clock. After 12 o'clock, you don't go to 13; you wrap back to 1. Modular arithmetic is clock arithmetic. It loops.

And because it loops, the sequence must eventually repeat. The number of steps before it repeats is called the period r.

Now here's the kicker: if you find r, and if r is even (which it usually is), then the factors of N can be extracted almost instantly using the formula:

gcd(x^r/2 − 1, N) and gcd(x^r/2 + 1, N)

That's it. The hard problem (factoring) has been reduced to a different problem (finding a period). And finding periods is something quantum computers are spectacularly good at.

Why? Because periodicity is a frequency question. And frequencies are where quantum interference shines.

The Four Steps—Where Quantum Magic Actually Happens

Step 1: Classical Preparation

Before any qubit gets involved, a regular computer picks a random number x between 2 and N−1. It checks whether gcd(x, N) = 1. If the gcd is already greater than 1, congratulations—you stumbled on a factor by pure luck. This almost never happens, but it's a free shortcut worth checking.

If gcd is 1, you proceed to the quantum part.

Step 2: Superposition—Loading Every Input at Once

A quantum register of qubits is placed into a superposition of all possible input values simultaneously. If you have n qubits, you get 2ⁿ states existing in parallel.

Don't think of this as "trying all answers at once" in the classical sense. That's a common oversimplification that leads to confusion later. Think of it more like this: you've laid out every possible input on a vast table, and the quantum computer is about to evaluate the modular exponentiation function on all of them at once, encoding the results into the quantum state's amplitudes.

The output register now contains a pattern: the modular sequence x^a mod N for every value of a, all encoded simultaneously. That pattern has a hidden rhythm—the period r. But it's buried in a superposition of thousands of overlapping values. You can't just "look" at it. Measuring now would give you one random snapshot, useless.

You need a way to extract the rhythm without destroying the pattern. Enter the quantum Fourier transform.

Step 3: The Quantum Fourier Transform—Finding the Beat in the Noise

This is the step most explanations gloss over or hide behind math. Let me build the intuition from scratch.

Imagine you're in a room with a hundred tuning forks, each vibrating at a slightly different frequency. If you strike them all simultaneously, the sound is chaos—a wall of noise. But if you had a device that could detect which frequencies are reinforcing each other and which are canceling out, you could isolate the dominant tone.

That's what the QFT does to quantum amplitudes.

After Step 2, the quantum state contains a periodic signal (the modular exponentiation results) buried among many values. The QFT performs a change of basis: it transforms the state from the "time domain" (which input produced which output) into the "frequency domain" (what is the repeating cycle length?).

Here's the physical mechanism: quantum interference. Each possible period contributes a wave-like amplitude. Paths corresponding to the wrong period arrive at the final measurement with phases that point in random directions—they cancel each other out, like noise-canceling headphones generating an inverted wave to kill ambient sound. Paths corresponding to the correct period arrive with phases that align—they constructively interfere, amplifying the signal like a guitar string resonating at its natural frequency.

After the QFT, if you measure the register, you get a value that is very likely a multiple of 1/r (or closely related to it). The wrong answers have been silenced by destructive interference. The right answer has been shouted into existence by constructive interference.

No classical computer can replicate this interference trick efficiently. It's not a matter of speed. It's a fundamentally different mode of computation.

Step 4: Measurement and Classical Extraction

You measure the output. You get a number. Using a classical technique called continued fraction expansion, you extract the period r from that measurement. Then you plug r into the formula, compute the gcd, and out pop your prime factors.

If the period turns out to be odd (bad luck), you go back to Step 1, pick a different x, and try again. On average, you'll succeed within a handful of attempts.

Classical vs. Quantum

That gap between "polynomial" and "sub-exponential" isn't a minor speedup. It's the difference between a problem being practically unsolvable and practically trivial. It's a phase transition in computational complexity.

Is RSA Encryption Dead?

No. Not even close. And this is where honest engineering meets theoretical elegance.

Shor's algorithm requires logical qubits—qubits that are effectively error-free. Current quantum hardware gives us physical qubits, which are noisy, fragile, and prone to decoherence. To build one reliable logical qubit, you need anywhere from hundreds to thousands of physical qubits running quantum error correction codes.

To factor a 2048-bit RSA key, estimates suggest you'd need roughly 4,000 to 20,000 logical qubits (depending on the architecture and error correction scheme). That translates to millions of physical qubits operating with gate fidelities well above 99.9%.

As of 2025, the largest quantum processors hover around 1,000–1,500 physical qubits, with error rates that still make large-scale fault-tolerant computation a distant engineering challenge. That said, the threat isn't zero. Nation-state actors can store encrypted data today and decrypt it later once hardware catches up—a strategy called "harvest now, decrypt later." This is exactly why the migration to Post-Quantum Cryptography (PQC) is already underway. NIST finalized its first batch of PQC standards in 2024, selecting lattice-based and hash-based schemes that resist quantum attacks.

The transition is happening. Slowly, imperfectly, but it's happening.

Frequently Asked Questions

Is Shor's algorithm polynomial time?

Yes. Its time complexity is O((log N)³), which is polynomial in the number of digits of N. This is what makes it revolutionary—classical factoring algorithms are super-polynomial, meaning the gap isn't just "faster" but belongs to an entirely different complexity class.

Can Shor's algorithm break AES-256?

No. Shor's algorithm targets problems based on integer factorization and discrete logarithms (RSA, Diffie-Hellman, elliptic curve cryptography). AES is a symmetric cipher. Quantum computers can attack AES using Grover's algorithm, which provides a quadratic speedup—effectively reducing AES-256 to the security level of AES-128. That's a weakening, not a break. Doubling your key length neutralizes it.

Why can't classical supercomputers simulate Shor's algorithm?

Because the quantum Fourier transform operates on a state space that grows exponentially with qubit count. Simulating 300 qubits requires tracking 2³⁰⁰ complex amplitudes—more numbers than there are atoms in the observable universe. The interference pattern that makes Shor's algorithm work is inherently a quantum phenomenon with no efficient classical analog.

Final Thought

The deepest lesson of Shor's algorithm isn't about cryptography. It's about the nature of computation itself.

Before 1994, we assumed that "hard problems" were hard because they required exploring an enormous search space. Shor showed that some problems are only hard because classical computers lack the right representational toolkit. Give a computer the ability to exploit interference and superposition, and a problem that looked like searching a desert for two specific grains of sand becomes listening for a single resonant frequency in a chord.

The hardware will catch up. Maybe in a decade, maybe in two. When it does, the locks we built on the assumption that factoring is hard will quietly, inevitably, come undone. The question isn't whether that day arrives. It's whether we'll be ready.