Shor's Algorithm

Shor’s algorithm, developed by Peter Shor in 1994, is the single most consequential result in quantum computing. It factors large integers in polynomial time: $O((\log N)^3)$ quantum operations. The best known classical algorithms for factoring take sub-exponential time, growing faster than any polynomial. For RSA-2048, the best classical methods require more computational work than the age of the universe allows. Shor’s algorithm, on a sufficiently large fault-tolerant quantum computer, would do it in hours.

RSA, ECDSA, and Diffie-Hellman key exchange all derive their security from the hardness of factoring or the related discrete logarithm problem. Shor’s algorithm breaks all of them.

The details

The algorithm works by reducing factoring to period finding. Given a number $N$ to factor and a random integer $a$ (coprime to $N$), the function:

$f(x) = a^x \bmod N$

is periodic with some period $r$. Once $r$ is found, it is often possible to compute factors of $N$ using classical number theory: if $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} \pm 1, N)$ gives a non-trivial factor of $N$ with high probability.

The quantum part finds $r$ efficiently using the Quantum Fourier Transform:

1. Prepare a superposition over all inputs: $\frac{1}{\sqrt{M}}\sum_{x=0}^{M-1}|x\rangle|0\rangle$

2. Apply the function in superposition using a quantum oracle: $\frac{1}{\sqrt{M}}\sum_{x=0}^{M-1}|x\rangle|f(x)\rangle$

3. Measure the second register. This collapses the first register into a superposition of all $x$ values that produce the same $f(x)$, which are spaced $r$ apart.

4. Apply the QFT to the first register. The QFT converts the periodic pattern into peaks at multiples of $M/r$ in frequency space.

5. Measure the first register. The result is a multiple of $M/r$; classical continued fractions algorithms recover $r$.

The circuit structure:

|0...0⟩ ──[H⊗n]──[U_f]──[QFT]──[M]──→ extract period r
|0...0⟩ ─────────[U_f]──────────[M]──→ (auxiliary register)

The QFT step is what provides the exponential speedup. The classical part (finding factors from the period) runs in polynomial time with no quantum resources.

Hardware requirements: Factoring RSA-2048 requires approximately $4{,}000$ logical qubits, implying roughly $4$ million physical qubits at current surface code overhead. Current largest processors have around $1{,}000$ physical qubits with no error correction.

Why it matters for learners

Shor’s algorithm is the primary motivation for the entire field of post-quantum cryptography. The threat it poses to RSA is why NIST spent eight years selecting and standardizing post-quantum algorithms. It is why intelligence agencies around the world are concerned about “harvest now, decrypt later” attacks.

Understanding Shor’s algorithm requires understanding superposition (to see why the quantum part works), the QFT (the engine of the speedup), and quantum circuits (to follow the circuit structure). It is an excellent capstone for a first quantum computing course.

The algorithm is also a clean example of how quantum speedup works: not by brute force, but by exploiting mathematical structure (periodicity) through a quantum transformation (QFT) that has no efficient classical equivalent.

Common misconceptions

Misconception 1: Shor’s algorithm currently threatens encryption. As of 2026, the largest integers factored by quantum hardware using Shor’s algorithm are in the range of 15 to 21. Factoring RSA-2048 requires millions of physical qubits with error correction. Current machines are several orders of magnitude away in both qubit count and quality.

Misconception 2: Shor’s algorithm can also break symmetric cryptography. Shor’s algorithm exploits specific number-theoretic structure (periodicity of modular exponentiation) that does not exist in symmetric encryption or hash functions. Grover’s algorithm provides a quadratic speedup on brute-force attacks, but this is addressed by doubling key lengths, not by replacing algorithms.

Misconception 3: The QFT is the hardest part to implement. The modular exponentiation step ($U_f$ in the circuit) is actually far more expensive in terms of gate count and circuit depth than the QFT. The QFT circuit uses $O(n^2)$ gates; the modular exponentiation requires $O(n^3)$ gates. Resource estimates for running Shor’s algorithm are dominated by the arithmetic circuits, not the QFT.

See also

• Quantum Fourier Transform
• Post-Quantum Cryptography
• Fault-Tolerant Quantum Computing
• Quantum Cryptography
• Grover’s Algorithm