Shor’s Algorithm Explained Without the Math

01Start 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.

02What He 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.

“

Factoring isn’t its own problem. It’s a period-finding problem wearing a disguise.

03Why 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 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.

How Shor breaks the lock

1. 01

   Disguise the problem

   Turn factoring into finding the period, the length of the cycle where a sequence of powers starts repeating.

2. 02

   Compute in superposition

   A quantum computer evaluates every power at once, like an instrument playing all notes together rather than stepping through them one by one.

3. 03

   Apply the Quantum Fourier Transform

   It extracts the rhythm from the noise. Every wrong period cancels out; the right one survives.

4. 04

   Measure

   Read the period, then a short classical calculation turns it into the factors. Period, factors, done.

04The Current Gap

An IBM-Stanford team demonstrated Shor’s algorithm on 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.

05Why 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 is what made cryptographers nervous in 1994, and kept them nervous for 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.

06What to Do With This

---

This article is educational and does not constitute security or investment advice.

// FAQ

What does Shor's algorithm actually break?

The two hard problems behind public-key cryptography: integer factoring (RSA) and discrete logarithm (Diffie-Hellman and elliptic-curve cryptography). It does not weaken symmetric encryption like AES or hash functions like SHA-256 the same way; those face Grover’s algorithm, which is far weaker.

Can Shor's algorithm break Bitcoin today?

No. It has only been demonstrated on tiny numbers (15, then 21). Breaking a real key needs millions of fault-tolerant qubits that no machine has. The algorithm is proven; the hardware is the gap.

Does a bigger RSA key help?

Only a little. Larger keys buy time but do not change the underlying vulnerability, because Shor scales efficiently. The fix is switching to post-quantum algorithms, not longer RSA keys.

What should I migrate to?

NIST’s finalized standards: ML-KEM (CRYSTALS-Kyber) for key exchange and ML-DSA (CRYSTALS-Dilithium) for signatures. Both rest on problems Shor’s algorithm cannot solve.