The Algorithm That Shook the Cryptographic World
In 1994, mathematician Peter Shor published an algorithm that sent shockwaves through the fields of cryptography and computer science. Shor's algorithm showed that a sufficiently powerful quantum computer could factor large integers exponentially faster than the best known classical algorithms. That might sound like a narrow mathematical achievement — but its implications are enormous.
The entire security of RSA encryption, one of the most widely used cryptographic systems on the internet, rests on the assumption that factoring large numbers is computationally intractable. Shor's algorithm breaks that assumption.
Why Factoring Matters for Encryption
RSA encryption is built on a simple mathematical asymmetry: multiplying two large prime numbers together is easy, but reversing the process — given only the product, find the two primes — is extremely hard for classical computers.
For example, multiplying two 1,024-bit prime numbers takes milliseconds. Factoring their product would take a classical computer longer than the age of the universe using the best known algorithms. This asymmetry is the security foundation for RSA keys used to protect banking, email, e-commerce, and government communications globally.
How Shor's Algorithm Works (Conceptually)
Shor's algorithm does not brute-force the factoring problem. Instead, it transforms it into a different mathematical problem — period finding — which quantum computers can solve efficiently using quantum Fourier transform.
Here's the high-level structure:
- Choose a random number a less than the number N to be factored.
- Find the period r of the function f(x) = aˣ mod N — i.e., the smallest r such that aʳ ≡ 1 (mod N).
- This period-finding step is performed using the quantum Fourier transform, giving an exponential speedup over classical methods.
- Once r is found, classical math can extract the prime factors of N with high probability.
The quantum speedup comes entirely from the period-finding step. Everything else is classical computation.
The Threat to Current Cryptography
Shor's algorithm is not just a threat to RSA. It also breaks elliptic-curve cryptography (ECC), which protects much of today's TLS/HTTPS traffic, digital signatures, and cryptocurrency transactions. The underlying vulnerability is the same: these systems rely on mathematical problems that Shor-type quantum algorithms solve efficiently.
Symmetric encryption (like AES) is less threatened — Grover's algorithm provides only a quadratic speedup for key searches, which can be mitigated by doubling key lengths (e.g., using AES-256 instead of AES-128).
How Powerful a Quantum Computer Would Be Needed?
This is the critical practical question — and the answer is reassuring for the near term. To factor a 2,048-bit RSA key using Shor's algorithm, estimates suggest a quantum computer would need roughly thousands to millions of logical qubits with very low error rates. Current state-of-the-art machines have hundreds to thousands of physical qubits with significant error rates — far from the fault-tolerant scale required.
The gap between today's NISQ devices and a cryptographically relevant quantum computer is substantial. Most estimates place this capability at least a decade away, though the timeline is genuinely uncertain.
The "Harvest Now, Decrypt Later" Risk
Even though cryptographically relevant quantum computers don't yet exist, a real threat exists today: adversaries may be collecting encrypted communications now, intending to decrypt them once quantum computers become available. This is known as the "harvest now, decrypt later" or "store now, decrypt later" (SNDL) attack strategy.
For information that must remain secret for many years — government communications, classified data, medical records — this is a genuine and urgent concern. It is a key reason why the transition to post-quantum cryptography must begin now, not when quantum computers arrive.
The Response: Post-Quantum Cryptography
The cryptographic community has been preparing. In 2024, NIST (National Institute of Standards and Technology) finalized the first post-quantum cryptographic standards, including:
- ML-KEM (formerly CRYSTALS-Kyber): A key encapsulation mechanism based on lattice problems.
- ML-DSA (formerly CRYSTALS-Dilithium): A digital signature scheme.
- SLH-DSA (formerly SPHINCS+): A hash-based signature scheme.
These algorithms are designed to resist attacks from both classical and quantum computers. Migration to these standards is underway across governments, cloud providers, and critical infrastructure — a transition that will take years to complete but must be treated as urgent.
Conclusion
Shor's algorithm is one of the most consequential mathematical discoveries of the late 20th century. It does not pose an immediate threat to today's encrypted systems, but it defines the destination the cryptographic world must reach before powerful quantum computers arrive. Understanding Shor's algorithm is understanding why post-quantum cryptography matters — and why the clock is already ticking.