Shor's Algorithm and the Future of Encryption

Peter Shor published his factoring algorithm in 1994 on hardware that did not yet exist. Thirty years later, that hardware still does not exist at the scale required. And yet Shor's algorithm remains one of the most consequential results in the history of computing — not because it has broken anything, but because it proved something could be broken.

A new episode of Qiskit in the Classroom, presented by Dr. Katie McCormick of IBM Quantum, works through the algorithm methodically: the mathematical foundations, the quantum machinery underneath, and a live demonstration factoring the number 15 on real IBM quantum hardware. It is a careful, honest piece of science communication. The demo works. The number 15 is not, to put it gently, a threat to global finance. But that is precisely the point McCormick is making — and the tension between what the algorithm demonstrates and what it implies is where the interesting questions live.

The lock and its key

Modern public-key cryptography, specifically RSA, rests on a mundane asymmetry: multiplying two large prime numbers together takes milliseconds, but reversing the operation — finding those two primes given only their product — is computationally ruinous for classical computers. The time required scales exponentially with the size of the number. RSA encodes your private key in that difficulty. As long as factoring is hard, the lock holds.

McCormick frames this with characteristic directness: every bank transaction, private message, and encrypted browser connection relies on the assumption that no one can efficiently factor a large number into its prime components. Shor's algorithm is a direct challenge to that assumption.

The insight Shor had in 1994 was to notice that factoring is not really the hard problem — order-finding is. Given a number N and a randomly chosen integer a that shares no common factors with N, the "order" of a is the smallest positive integer r such that a^r is congruent to 1 modulo N. These modular exponentiation sequences are periodic — they behave like a clock, cycling back to one — and the period encodes information about N's prime factors.

McCormick walks through the algebra that shows why: if you find an even-order r, you can construct a number x = a^(r/2) whose square is congruent to 1 mod N but which is not itself congruent to ±1. That condition forces the prime factors p and q to split across the expressions (x+1) and (x−1), making them recoverable via two greatest common divisor calculations — operations that are trivially fast. The hard part is finding r in the first place. Classically, that scales exponentially. Quantum mechanically, it does not.

Where quantum actually helps

The quantum portion of Shor's algorithm is confined to a single subroutine: quantum phase estimation (QPE), which finds the period of the modular function. This is not a case of quantum computers being generically faster; they are specifically, structurally suited to period-finding in a way classical machines are not.

QPE works by encoding the modular multiplication operation as a unitary operator and then using quantum interference to extract its eigenvalues. Those eigenvalues contain the period. The trick that makes this tractable — and which McCormick describes as the algorithm's most elegant move — is that you do not need to prepare the eigenstate of the operator in advance. The state |1⟩ is already an equal superposition of all the relevant eigenstates. You start there, run phase estimation, and the quantum measurement collapses to an approximation of j/r for some random j. Repeat enough times, and continued fraction methods extract r.

"It may make sense when you work through it step by step," McCormick says, "but I still find it incredible that Shor had the insight to see all of this in the first place."

That incredulity is earned. The path from "factoring is hard" to "find the period of a modular function using quantum interference" is not obvious. It required seeing through the stated problem to a hidden mathematical structure underneath — and then recognizing that quantum computers were precisely the tool to exploit that structure.

The demo, and what it honestly shows

The live demonstration factors 15 using a = 2. McCormick is explicit about a shortcut taken for manageability: the modular multiplication circuit is constructed using prior knowledge of the answer, rather than being built from scratch via general modular exponentiation. This would not be permissible in a cryptographic attack scenario, where the whole point is that you do not know the factors. She calls it "cheating a little bit" and identifies it as the location of the real engineering challenge in any practical implementation.

The histogram output from the quantum computer shows four clear peaks — corresponding to the four periodic states — with additional noise from quantum hardware imperfections. Classical post-processing extracts a factor of 3 on the first attempt. Fifteen divided by three is five. Done.

It is a satisfying demonstration of the algorithm's logic. It is emphatically not a demonstration of cryptographic threat. The gap between factoring 15 and factoring the 2048-bit integers used in RSA is not a detail; it is a difference that no incremental hardware improvement bridges. What it takes to close that gap — fault-tolerant quantum computing with millions of high-quality logical qubits — remains an unsolved engineering problem, not a solved one approaching deployment.

The two wrong framings

Coverage of quantum computing and encryption tends to collapse into one of two errors. The alarmist version treats Shor's algorithm as an imminent catastrophe, implying that encryption is already compromised or will be shortly. The dismissive version points at factoring 15 and concludes the whole field is hype, safely ignorable. McCormick's episode threads between them, and the threading is instructive.

The alarmist framing ignores where the hardware actually is. McCormick notes that even after 30 years of remarkable progress, quantum computers do not yet operate at the scale required — and that fault tolerance, the threshold that would make large-scale execution viable, has not been reached. Timelines that place Q-day — the hypothetical moment when quantum hardware can crack RSA in practice — within the next several years should be read with that context in hand.

But the dismissive framing makes its own error, one worth naming precisely: it mistakes the current state of hardware for a verdict on the algorithm's significance, and in doing so ignores that cryptographic infrastructure has decade-long replacement cycles. You do not wait until the attack is live to migrate. The standards body NIST finalized its first post-quantum cryptographic standards in 2024, and quantum-safe protocols have been in active development at IBM and elsewhere for years. That work is not happening because researchers are panicking — it is happening because the people who understand the math recognize that "not yet" is not the same as "not ever," and that migration at scale takes time that must be borrowed now.

"This single algorithm broke open the floodgates of quantum computing as a serious field," McCormick says. "And the clever algorithms that followed wouldn't exist without it."

That framing is accurate. Shor's algorithm did not arrive as an engineering solution — it arrived as a proof of concept that redrew the map of what computation could do. It told cryptographers they were living on borrowed time and told quantum computing researchers they had a mandate. Both communities responded accordingly.

What comes next

The episode ends with McCormick pointing toward fault tolerance as the threshold: once quantum hardware crosses into the fault-tolerant regime, algorithms like Shor's will follow close behind. That is probably the right mental model — not a cliff edge where encryption falls overnight, but a transition zone where quantum advantage becomes reliable enough to matter, and where the post-quantum migration either has or has not been completed.

The unsatisfying truth is that nobody knows exactly when fault tolerance arrives. Hardware is improving, error correction theory is maturing, and the engineering constraints are better understood each year. But "better understood" and "solved" are different things.

What Shor's algorithm actually broke, in 1994, was not RSA. It was the assumption that computational hardness was a permanent feature of mathematics rather than a contingent fact about the machines we happened to have built. That is the shift that matters — and thirty years on, its implications are still being worked out.

---

Priya Sharma is a science and health correspondent for BuzzRAG.