Shor's Algorithm

Shor's Algorithm is a quantum algorithm for integer factorization that runs in polynomial time — specifically O((log N)³) — destroying the computational hardness assumption on which RSA encryption and the entirety of modern public-key infrastructure depend. It was published by Peter Shor in 1994 and remains the most consequential result in the theory of quantum computation: proof that complexity classes are not fixed mathematical truths but contingent facts about the physical laws of the universe.

The Problem It Solves

The security of RSA rests on a belief: that factoring the product of two large primes is computationally intractable for any machine running classical algorithms. The best classical factoring algorithm (the general number field sieve) runs in sub-exponential time — fast enough to make factoring small numbers routine, slow enough to make factoring 2048-bit numbers beyond reach for any foreseeable classical computer. The belief that this asymmetry is permanent underpins trillions of dollars of encrypted commerce and government communication.

Shor's Algorithm renders that belief false — conditionally on the construction of a sufficiently large fault-tolerant quantum computer. It factors an N-bit integer in O(N³) quantum gate operations, a polynomial overhead compared to the exponential cost of the best classical alternatives. The algorithm does not merely improve on classical methods; it invalidates the assumption that the problem is hard.

Structure of the Algorithm

Shor's Algorithm reduces integer factorization to the problem of finding the period of a modular exponentiation function. This reduction is classical — it uses elementary number theory. The quantum subroutine is a period-finding machine.

Given an integer n to factor and a randomly chosen integer a coprime to n, the function f(x) = aˣ mod n is periodic with period r (the multiplicative order of a modulo n). Once r is known, classical probability theory guarantees that gcd(aʳ/² − 1, n) yields a non-trivial factor of n with probability at least 1/2, absent degenerate cases.

Finding the period classically requires evaluating f for exponentially many values of x. The quantum subroutine achieves this in polynomial time using:

1. Quantum Fourier Transform (QFT): the quantum analog of the Discrete Fourier Transform, implemented with O(N²) quantum gates. The QFT transforms superpositions of computational basis states into superpositions of frequency basis states. Applied to the periodic function f, it concentrates probability amplitude near multiples of N/r — allowing measurement to yield an integer close to kN/r for random k.
2. Phase estimation: repeated measurements and classical continued-fraction expansion extract r from the sampled kN/r values with high probability.

The Quantum Fourier Transform is not magic. It is unitary linear algebra over complex-valued amplitudes, arranged so that the periodicity of f creates constructive interference at the correct frequencies and destructive interference elsewhere. The algorithm exploits interference — not parallelism in the naive sense. A quantum computer running Shor's Algorithm does not try all possible factors simultaneously; it arranges amplitudes so that the wrong answers cancel.

Cryptographic Consequences

The deployment of a cryptographically relevant quantum computer — one with enough fault-tolerant logical qubits to run Shor's Algorithm against 2048-bit RSA keys — would break RSA, Diffie-Hellman, and elliptic-curve cryptography simultaneously. These are not edge-case systems. They are the authentication backbone of HTTPS, SSH, email signing, software distribution, and financial settlement.

Post-Quantum Cryptography exists because of this threat. NIST finalized its first post-quantum cryptographic standards in 2024: CRYSTALS-Kyber (key encapsulation), CRYSTALS-Dilithium, FALCON, and SPHINCS+ (digital signatures). These algorithms replace the hardness of factoring or discrete logarithm with problems believed to resist quantum attack — primarily Lattice-Based Cryptography and hash-based constructions.

The transition is not trivial. Cryptographic infrastructure is deeply embedded. The concern is not only future quantum attacks but harvest now, decrypt later: adversaries who record encrypted traffic today, intending to decrypt it once quantum hardware matures. Traffic encrypted today with RSA that must remain confidential for ten or more years is already potentially compromised.

Current State of the Threat

As of 2026, no quantum computer has factored an integer larger than a few thousand bits. The engineering gap between current noisy intermediate-scale quantum (NISQ) devices and the fault-tolerant machines required for cryptographically relevant factoring is measured in multiple orders of magnitude — in qubit count, gate fidelity, and coherence time simultaneously. Quantum Error Correction theory is mature; the engineering is not.

Estimates of the timeline vary by orders of magnitude. This uncertainty is not reassuring. The correct response to catastrophic irreversible risk under timeline uncertainty is to migrate infrastructure — not to wait for the threat to be concrete.

What the Algorithm Reveals

Shor's Algorithm is a fact about complexity theory, not merely a practical threat. It proves that the complexity class BQP (problems efficiently solvable by quantum computers) contains integer factorization, and that if factoring is truly hard for classical computers, then P ≠ BQP — quantum computers are genuinely more powerful for some problems. This is one of the few results in complexity theory with unambiguous real-world stakes.

The deeper implication: what counts as computationally hard depends on what kind of physical machine you are allowed to build. Information-theoretic hardness is not hardness; only computational hardness relative to a physical model matters. The universe, at its quantum mechanical substrate, permits computations that classical physics does not. Shor's Algorithm is a probe of that substrate — a demonstration that our choice of computational model has been quietly wrong about what counts as difficult.

Any civilization that built RSA-based infrastructure without seriously engaging with quantum computation theory was reasoning inside an insufficiently physical model of computation. The alarm was available in 1994. The migration remains incomplete in 2026.