Shor's Algorithm

Definition

Shor's algorithm, discovered by Peter Shor in 1994, is a quantum algorithm that factors integers in polynomial time — specifically $O((\log N)^3)$ gate operations for an $N$-bit integer. This is exponentially faster than the best known classical algorithm (the general number field sieve, which runs in subexponential time $\exp(O((\log N)^{1/3}))$). Because RSA encryption derives its security from the hardness of integer factorisation, a large-scale quantum computer running Shor's algorithm would break RSA-2048 in hours — a task estimated to take trillions of years on classical hardware.

Algorithm Outline

Shor's algorithm reduces factorisation to the order-finding problem: given $N$ (the number to factor) and a random $a$ coprime to $N$, find the smallest $r$ such that $a^r \equiv 1 \pmod N$. Once $r$ is found, the factors are $\gcd(a^{r/2} \pm 1, N)$.

The algorithm proceeds in five steps:

Step 1: Classical Preprocessing

If $N$ is even, or if $N = p^k$, the factors are trivial. Otherwise, choose a random $a \in \{2, 3, \dots, N-2\}$ such that $\gcd(a, N) = 1$.

Step 2: Quantum Order Finding

Prepare a quantum circuit with two registers:

• Register 1: $2n$ qubits (where $n = \lceil \log_2 N \rceil$), initialised to $|0\rangle^{\otimes 2n}$.
• Register 2: $n$ qubits, initialised to $|1\rangle$ (or $|0\rangle^{\otimes n}$ for the modular exponentiation).

The circuit performs:

1. Superposition: Apply Hadamard gates to all qubits in Register 1:

   $\displaystyle H^{\otimes 2n} |0\rangle^{\otimes 2n} = \frac{1}{\sqrt{2^{2n}}} \sum_{x=0}^{2^{2n}-1} |x\rangle$

2. Modular exponentiation: Compute $a^x \bmod N$ into Register 2:

   $\displaystyle \frac{1}{\sqrt{2^{2n}}} \sum_{x=0}^{2^{2n}-1} |x\rangle |a^x \bmod N\rangle$

3. Inverse quantum Fourier transform (QFT†): Apply the inverse QFT on Register 1, causing interference that peaks at values of $x$ that are multiples of $2^{2n} / r$.

4. Measurement: Measure Register 1. The outcome $y$ is (with high probability) close to $s \cdot 2^{2n} / r$ for some integer $s$.

Step 3: Classical Postprocessing

From the measured $y$, use the continued fractions algorithm to extract $r$ (the order).

Step 4: Check the Result

If $r$ is even and $a^{r/2} \not\equiv \pm 1 \pmod N$, compute:

$\displaystyle \gcd(a^{r/2} - 1, N) \quad \text{and} \quad \gcd(a^{r/2} + 1, N)$

One of these is a non-trivial factor of $N$.

Step 5: Retry if Necessary

The algorithm succeeds with probability $> 1/2$ (or $> 99\%$ with a few repeats). If it fails, choose a different $a$ and repeat.

Circuit Diagram (Simplified)

|0⟩ — H —●—————————————————————— QFT† — M —
|0⟩ — H —●—————————————————————— QFT† — M —
 ⋮        ⋮                                ⋮
|0⟩ — H —●—————————————————————— QFT† — M —
         │
|1⟩ ———╲_U╱———————————————————————————————
       a^x mod N

Where $U$ is the unitary that computes $a^x \bmod N$.

Resource Estimates

Estimates from Gidney & Ekerå (2021) using surface-code error correction and lattice-surgery operations.

Impact on Cryptography

Shor's algorithm breaks the following public-key cryptosystems:

Countermeasure: Post-quantum cryptography (PQC) — NIST-standardised algorithms (ML-KEM, ML-DSA, SLH-DSA) are not vulnerable to Shor's algorithm because they are based on lattice problems and hash functions.

Variants and Generalisations

• Shor's algorithm for discrete logarithms: A direct adaptation solves the discrete logarithm problem in abelian groups (relevant for ECDH/ECDSA) using a nearly identical circuit structure.
• Hidden subgroup problem (HSP): Both Shor's and Grover's algorithms are special cases of the abelian hidden subgroup problem. Shor solves the cyclic group HSP; the discrete-log variant solves the product-of-cyclic-groups HSP.
• Variational factorialisation (VQF): A NISQ-era heuristic that uses a variational quantum eigensolver to factor small numbers (up to ~20 bits) but lacks Shor's provable exponential speedup.

Resources and References

• Shor, "Algorithms for quantum computation: Discrete logarithms and factoring" (1994), FOCS 1994, 124–134. [Original paper]
• Gidney & Ekerå, "How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits" (2021), Quantum 5, 433. [Leading resource estimate]
• Quantum circuit implementations: qiskit.org/ecosystem/algos — Qiskit Algorithms includes modular exponentiation circuits.
• Beauregard, "Circuit for Shor's algorithm using 2n+3 qubits" (2002), arXiv:quant-ph/0205095. [Optimised qubit count]