Shor’s Algorithm Explained Without the Math

RSA encryption runs most of the internet. Every padlock in a browser, every bank login you’ve ever made runs on it or something built from the same foundations. Peter Shor’s 1994 paper is why that’s ending.

The maths takes years. What follows skips all of it and gets straight to the idea.

Start With the Lock

RSA works because multiplication is easy and reversal is brutal.

Take two primes: 17 and 19. Multiply them: 323. Done in a second. Now someone hands you 323 and asks which two primes were multiplied to get there. Harder. Still doable for small numbers, but scale this to RSA-2048, where the public number has 617 decimal digits, and a classical computer grinding through all possible prime factors would need longer than the current age of the universe to finish.

That’s the lock.

Your public key is the big product. Anyone can encrypt with it. Only you hold the two primes that produced it, and those primes are the private key that decrypts everything. The whole system’s security rests on one assumption: factoring is hard.

Mathematician Peter Shor proved the assumption wrong. On a quantum computer, factoring is a solved problem. Shor has a version for discrete logarithm too. Elliptic-curve cryptography (ECC), which underpins most HTTPS connections, relies on a related problem called discrete logarithm. Shor’s algorithm breaks that too.

What He Actually Figured Out

He found something more interesting than a faster factoring method: the factoring problem is a different problem wearing a disguise.

A period-finding problem.

Take a number, say 7, and compute its powers modulo some large number N. Modulo just means the remainder after dividing. 7² mod N, 7³ mod N, 7⁴ mod N, and so on. The remainders eventually repeat. They cycle. That cycle length, the period, contains enough mathematical structure to pull the factors of N directly out of it, through a short classical calculation that takes milliseconds once you have it.

The catch: finding that period classically means grinding through millions of values one at a time before the pattern surfaces. Still hard. Which is where quantum mechanics enters.

Why Waves Solve It

Superposition is the word that gets mangled most, and it’s the most important one.

A quantum computer in superposition is more like an instrument playing every note simultaneously than a parallel processor stepping through options in sequence. Every value of 7^k mod N, computed together, instantaneously.

Useless on its own. Measure a quantum system in superposition and you get one random answer pulled from the noise.

The actual trick in Shor’s design is what happens before measurement. He applied a quantum operation called the Quantum Fourier Transform. Without any equations: imagine you’re staring at a noisy signal and you need to find its underlying frequency. A Fourier Transform extracts the rhythm from the chaos. Shor’s version does the same thing. Every wrong period cancels out. The right one survives.

Measure. Period. Factors. Done.

The Current Gap

An IBM-Stanford team demonstrated Shor’s algorithm on actual quantum hardware in 2001. The number they factored was 15. Meaning: 3 × 5.

Researchers have since managed 21.

Shor’s algorithm demonstrably works. But the distance between factoring 21 and cracking a 617-digit RSA key is almost impossible to frame usefully: millions of fault-tolerant logical qubits that stay coherent through a computation today’s noisy hardware can’t sustain past a handful of gates. Google’s best current machines have hundreds of physical qubits, most too error-prone for Shor’s to run reliably.

This changed in 2025. A 2024 Google research paper on qLDPC codes showed qLDPC error-correction codes cut the overhead required for fault-tolerant qubits by a factor of 161. Resource estimates shrank dramatically. It’s why Google set 2029 as its post-quantum migration deadline.

Hardware is the only thing still catching up. For now.

Why 1994 Is an Important Year

Shor published when quantum computers barely existed as physical objects. Most researchers at the time thought quantum computing was a mathematical curiosity that might never produce anything practically useful. His paper ended that read overnight.

It proved they could dissolve problems that classical computers fundamentally cannot solve within any timeframe that matters, not given centuries of improvement, not given better hardware or compilers. A different class of problem. That distinction is what made cryptographers nervous in 1994 and kept them nervous for the next three decades.

NIST finalized its first 3 post-quantum cryptographic standards in 2024. Thirty years after Shor’s paper. Whether that lag is institutional inertia or a sustained bet that quantum hardware would stay too noisy to matter, the bet is getting visibly harder to defend.

What to Do With This

If you run infrastructure encrypting data that needs to stay confidential for more than 5 years, Shor’s is already your problem.

The “harvest now, decrypt later” threat model doesn’t require quantum computers to exist today. Adversaries are stockpiling RSA-encrypted traffic right now. They can’t read it yet. The plan is to store it until a working CRQC exists, then run everything through in one pass and decrypt years of accumulated data. That attack became theoretically viable the day Shor published. The hardware is the gap.

Bigger RSA keys buy a little time but don’t change the underlying vulnerability. Migrate. CRYSTALS-Kyber and CRYSTALS-Dilithium are the NIST-finalized options; both rely on mathematical problems Shor’s algorithm can’t touch, and getting there typically takes 7-10 years from the moment an organization decides to start.

Start the migration. The window is probably shorter than the 7-10 year runway most organizations need to act.