Shor’s Algorithm: The Quantum Computer’s Favorite Way to Ruin RSA’s Day

For decades, modern cryptography has rested on a comforting assumption that factoring really large numbers is hard.

Not “hard” in the sense of assembling IKEA furniture.

Not “hard” in the sense of understanding your health insurance policy.

Hard in the sense that even the world’s fastest supercomputers would need absurd amounts of time to factor the enormous numbers used by RSA.

This was wonderful news for everyone who enjoyed secure banking, encrypted websites, and not having their passwords stolen by bored teenagers.

Then quantum computing arrived and said that’s cute.

And thus entered Shor’s Algorithm, the mathematical equivalent of showing up to a vault door carrying a master key.

Shor’s Algorithm is a quantum computing algorithm developed by Peter Shor in 1994 that can efficiently solve certain mathematical problems — most notably the factoring of large integers. That may sound about as exciting as watching paint dry on a calculus textbook, but it’s a very big deal because the security of RSA, one of the most widely used public-key cryptosystems in history, depends on factoring being incredibly difficult. Shor’s Algorithm showed that a sufficiently powerful quantum computer could turn that supposedly impossible task into a practical one, effectively threatening decades of cryptographic assumptions and sending security researchers everywhere into a collective panic-induced sprint toward post-quantum cryptography.

The Problem Nobody Wanted To Hear About

In 1994, mathematician and computer scientist Peter Shor published an algorithm that changed everything.

He demonstrated that a sufficiently powerful quantum computer could factor large integers in polynomial time.

This is the cryptographic equivalent of discovering that bank vaults are vulnerable to a very specific species of wizard.

For classical computers, factoring gets painfully difficult as numbers grow larger.

For a quantum computer, running Shor’s Algorithm factoring becomes dramatically easier.

And suddenly RSA begins sweating nervously.

The Magic Trick Behind Shor’s Algorithm

At first glance, Shor’s Algorithm appears to be about factoring.

But that’s not actually the problem it solves.

Instead, it solves something called period finding.

Because apparently factoring wasn’t complicated enough.

Suppose we choose a number:

a

and repeatedly compute:

a¹ mod Na² mod Na³ mod Na⁴ mod N

Eventually the results begin repeating.

That repetition interval is called the period.

For example:

2¹ mod 15 = 22² mod 15 = 42³ mod 15 = 82⁴ mod 15 = 12⁵ mod 15 = 2

The cycle repeats every four steps.

The period is:

r = 4

A classical computer can find periods. Slowly.

A quantum computer can find them with shocking efficiency. And, that’s where the trouble begins.

The Quantum Part

This is where explanations usually become dangerous.

Most articles start throwing around words like:

• Superposition
• Interference
• Hilbert spaces
• Unitary transformations

Readers immediately begin questioning their life choices.

Let’s keep it simple.

A classical computer evaluates possibilities one at a time.

A quantum computer creates a state that represents many possibilities simultaneously.

Before anybody writes angry emails:

• No, it is not literally trying every answer at once.
• No, it is not exploring alternate dimensions.
• No, your quantum laptop is not secretly communicating with parallel universes.

The reality is both more complicated and less exciting.

What matters is that quantum mechanics allows certain computations to be structured in ways that reveal hidden mathematical patterns extraordinarily efficiently.

I explore this further in my “Introduction To Quantum Computing: Because Regular Computers Apparently Weren’t Complicated Enough” blog post.

Shor’s Algorithm exploits exactly that.

The Quantum Fourier Transform

Every good cryptographic apocalypse requires a complicated-sounding mathematical tool.

Shor’s Algorithm uses the Quantum Fourier Transform (QFT). For reference check out regular Fourier Transforms.

Think of it as a pattern-finding machine.

The quantum computer creates a state containing information about many possible values. The QFT then amplifies information about the period hidden within those values.

Somehow an innocent-looking sequence of modular arithmetic gets transformed into information that reveals the factorization of a giant number.

Mathematicians think this is beautiful; everyone responsible for public-key infrastructure thinks it is mildly terrifying.

Why RSA Is In Trouble

Once the period is known, some additional number theory can often produce the factors of N.

Those factors reveal:

p

and

q

The secret ingredients of RSA.

And once you know p and q, game over. The private key can be reconstructed.

The vault door swings open. The dragon guarding the treasure gets fired.

But, How Bad Is It?

Today? Not very. Current quantum computers are nowhere near large enough to break modern RSA keys.

The challenge isn’t just running Shor’s Algorithm. It’s running Shor’s Algorithm on a sufficiently large, fault-tolerant quantum computer with millions of reliable logical qubits.

That’s still a significant engineering challenge. The meteor has been spotted; it just hasn’t arrived yet.

The Weirdest Part

Perhaps the strangest thing about Shor’s Algorithm is that it didn’t break RSA by directly attacking RSA. Instead, it found an efficient solution to a completely different mathematical problem.

Then number theory did the rest.

It’s like defeating a castle by learning advanced flute techniques and somehow ending up with the keys to the gate.

The connection makes perfect sense to mathematicians, which should immediately make the rest of us suspicious.

Summary

For nearly fifty years, RSA stood as one of humanity’s greatest cryptographic achievements. Its security relied on the assumption that factoring large numbers was unimaginably difficult.

Then Peter Shor came along and proved that quantum mechanics had other ideas.

Today, Shor’s Algorithm remains one of the most important discoveries in both cryptography and quantum computing.

Not because it has broken RSA.

Not yet.

But, because it showed that one of the foundations of modern digital security is living on borrowed time, which is a little unsettling.

On the bright side, at least we got some really interesting mathematics out of it.

Notes

• AI / GenAI / ChatGPT / etc were not used to generate the text of this article.
• ChatGPT was used to generate the images.
• I used em dashes in my writing before the current GenAI wave was a thing. Not planning on changing now.
• Names have been changed to protect the guilty.
• None of the hostnames or users used in examples actually exist.
• Feel free to post any comments or suggestions below.