What Is Shor’s Algorithm?

Most of the secrets that keep modern life running—bank transfers, private messages, the little padlock in your browser’s address bar—are protected by math that today’s computers cannot solve in any reasonable amount of time. Shor’s algorithm is the reason cryptographers worry that this won’t last.

Devised in 1994 by mathematician Peter Shor, then at Bell Labs, the algorithm is a recipe for a quantum computer to do something classical machines cannot: factor enormous numbers quickly. That sounds academic, but it strikes at the foundation of how we secure information.

The Math Behind the Lock

Much of today’s encryption, including the widely used RSA system, rests on a simple asymmetry. Multiplying two large prime numbers together is easy. Reversing the process—taking the giant result and figuring out which two primes produced it—is staggeringly hard. For a number hundreds of digits long, the world’s fastest supercomputers would need longer than the age of the universe to crack it by brute force.

Shor’s algorithm changes that calculus. By exploiting the strange properties of quantum mechanics, where bits can occupy multiple states at once, it finds those hidden prime factors exponentially faster. A sufficiently powerful quantum computer running Shor’s algorithm could, in principle, unravel encryption that would otherwise be unbreakable.

The threat is not yet here. Breaking real-world encryption would require a quantum machine with millions of stable, error-corrected qubits—the quantum equivalent of bits. Today’s most advanced quantum computers operate with only a few hundred error-prone qubits. Most experts believe a code-breaking machine is years, possibly more than a decade, away.

But the timeline is not the whole story. Adversaries can intercept and store encrypted data now, then decrypt it later once the hardware catches up—a strategy security experts call “harvest now, decrypt later.” Sensitive information with a long shelf life, such as state secrets or medical records, is effectively at risk today.

Why Shor’s Algorithm Matters for PQC

This looming threat is the entire reason for post-quantum cryptography, or PQC: a new generation of encryption designed to withstand quantum attacks. Rather than waiting on hardware that doesn’t yet exist, PQC takes a different tack. It builds locks based on math problems that even a quantum computer would struggle to solve.

Shor’s algorithm is exceptional at factoring numbers and a related problem called discrete logarithms. It is not, however, a universal codebreaker. PQC schemes lean on entirely different puzzles—such as finding patterns hidden in high-dimensional mathematical lattices—that have no known quantum shortcut.

In 2024, the U.S. National Institute of Standards and Technology finalized its first set of post-quantum encryption standards, giving companies and governments a blueprint for the switch. The migration—replacing cryptography woven into nearly every digital system, from web browsers to banking networks—will take years of careful work.

Shor’s algorithm has not broken anything yet. But it has already rewritten the rules, forcing the world to rebuild its defenses before the threat arrives.