Prerequisite: Grover’s Algorithm

Why Factoring Matters

RSA encryption relies on the assumption that factoring an $n$-bit integer $N = pq$ is computationally hard. The best known classical algorithm, the General Number Field Sieve (GNFS), runs in sub-exponential time:

$$T_{\text{GNFS}} = O!\left(\exp!\left(c,(\log N)^{1/3}(\log\log N)^{2/3}\right)\right)$$

for a constant $c \approx 1.9$. For a 2048-bit RSA modulus this is still astronomically large classically, which is why RSA-2048 is considered secure today.

Shor’s algorithm (1994) factors $N$ in quantum time $O((\log N)^3)$, achieving an exponential speedup. This would render all RSA, Diffie-Hellman, and elliptic-curve cryptography insecure on a sufficiently large fault-tolerant quantum computer.

Reduction: Factoring to Order Finding

The quantum part of Shor’s algorithm solves a number-theoretic subroutine. The classical reduction proceeds as follows.

  1. Pick a random integer $1 < a < N$ with $\gcd(a, N) = 1$ (if $\gcd(a, N) > 1$ we have already found a factor).
  2. Find the order $r$ of $a$ modulo $N$: the smallest positive integer satisfying

$$a^r \equiv 1 \pmod{N}$$

  1. If $r$ is odd or $a^{r/2} \equiv -1 \pmod{N}$, restart with a new $a$.
  2. Otherwise, compute $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2} + 1, N)$.

Why this works. From $a^r \equiv 1$ we get $(a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}$. Since $N = pq$, one of $p, q$ must divide $a^{r/2} - 1$ and the other $a^{r/2} + 1$ (or both divide one, but this has probability at most $1/2$ over random $a$). A GCD computation then extracts a non-trivial factor in $O((\log N)^2)$ classical operations.

Number-theoretic analysis shows that a random $a$ yields a useful $r$ with probability at least $1/2$, so $O(\log \log N)$ repetitions suffice for constant failure probability. The bottleneck is computing $r$, which is where quantum computation enters.

The Order-Finding Subroutine

Define the unitary operator:

$$U|x\rangle = |ax \bmod N\rangle, \quad x \in {0, 1, \ldots, N-1}$$

extended arbitrarily for $x \geq N$. The key insight is that $U$ has a natural spectral structure. Its eigenstates are:

$$|u_s\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1} e^{-2\pi i sk/r}|a^k \bmod N\rangle, \quad s = 0, 1, \ldots, r-1$$

with eigenvalues $e^{2\pi i s/r}$:

$$U|u_s\rangle = e^{2\pi i s/r}|u_s\rangle$$

Phase estimation on $U$ with input $|1\rangle$ (which equals $\frac{1}{\sqrt{r}}\sum_s |u_s\rangle$ by the Fourier inversion formula) measures a random eigenphase $s/r$ with $s$ uniform in ${0, \ldots, r-1}$. Continued-fraction expansion of the measured approximation then recovers $r$ with high probability.

The Quantum Fourier Transform

The Quantum Fourier Transform (QFT) over $\mathbb{Z}_M$ is defined by its action on computational basis states:

$$\text{QFT}|j\rangle = \frac{1}{\sqrt{M}}\sum_{k=0}^{M-1} e^{2\pi ijk/M}|k\rangle$$

For $M = 2^n$, the QFT decomposes into $n$ Hadamard gates and $n(n-1)/2$ controlled phase rotations $R_k = \begin{pmatrix} 1 & 0 \ 0 & e^{2\pi i/2^k} \end{pmatrix}$, giving $O(n^2)$ gates total. With approximate QFT (dropping rotations below threshold $2^{-m}$), the gate count reduces to $O(n \log n)$.

Compare to the classical FFT, which requires $O(n \cdot 2^n)$ operations for the same transform on $2^n$ amplitudes. The quantum speedup is exponential because the QFT acts on a superposition of all $2^n$ basis states simultaneously, but the exponential superposition is not directly accessible: one can only measure the result.

The $n$-qubit QFT circuit (most-significant qubit first):

  1. Apply $H$ to qubit $1$.
  2. Apply controlled-$R_2$ with control qubit $2$, target qubit $1$.
  3. Apply controlled-$R_3$ with control qubit $3$, target qubit $1$. Continue through $R_n$.
  4. Apply $H$ to qubit $2$, then controlled-$R_2$ through $R_{n-1}$, and so on.
  5. Reverse the qubit order with SWAP gates.

Phase Estimation for Order Finding

The quantum order-finding circuit uses two registers: a first register of $t = 2n + O(\log(1/\epsilon))$ qubits (to approximate $s/r$ to $n$ bits of precision with error probability $\leq \epsilon$), and a second register of $n$ qubits holding values modulo $N$.

Full circuit:

  1. Initialise both registers: $|0\rangle^{\otimes t}|1\rangle$.
  2. Apply $H^{\otimes t}$ to the first register: $\frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t - 1}|j\rangle|1\rangle$.
  3. Apply controlled-$U^{2^k}$ for $k = 0, 1, \ldots, t-1$ (controlled on the $k$-th qubit of the first register). This produces:

$$\frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle,U^j|1\rangle = \frac{1}{\sqrt{2^t}}\sum_{j=0}^{2^t-1}|j\rangle|a^j \bmod N\rangle$$

  1. Apply the inverse QFT to the first register.
  2. Measure the first register to obtain an integer $\tilde{y}$ close to $2^t \cdot s/r$ for a random $s$.
  3. Apply the continued-fraction algorithm to $\tilde{y}/2^t$ to recover the fraction $s/r$ in lowest terms; extract $r$ as the denominator.

Modular exponentiation. The controlled-$U^{2^k}$ gates implement $|j\rangle|x\rangle \to |j\rangle|a^j x \bmod N\rangle$. Each $U^{2^k}$ is realised via repeated squaring: precompute $a^{2^k} \bmod N$ classically, then perform controlled modular multiplication. The full sequence uses $O(n)$ multiplications, each costing $O(n^2)$ quantum gates, giving $O(n^3)$ total gates.

Complexity Analysis

Component Quantum gates Classical ops
QFT (inverse) $O(n^2)$ -
Modular exponentiation $O(n^3)$ -
GCD and continued fractions - $O(n^2)$
Total per attempt $O(n^3)$ $O(n^2)$

With $O(\log\log N) = O(\log n)$ attempts, the overall complexity is $O(n^3 \log n)$, dominated by modular exponentiation. Using fast quantum arithmetic (Schönhage-Strassen style), this improves to $O(n^2 \log n \log\log n)$.

Correctness: Continued Fractions

After measurement, we obtain $\tilde{y}$ satisfying $|\tilde{y}/2^t - s/r| \leq 1/2^{t+1}$. Since $r < N < 2^n$ and $t \geq 2n$, the fraction $s/r$ is the unique rational with denominator $< N$ within $1/(2N^2)$ of $\tilde{y}/2^t$. The continued-fraction algorithm (Euclidean-algorithm based) recovers $s/r$ in reduced form in $O(n^2)$ time. The denominator is $r/\gcd(s,r)$; since $s$ is uniform in ${0,\ldots,r-1}$, the probability that $\gcd(s,r) = 1$ (yielding $r$ directly) is $\phi(r)/r \geq \Omega(1/\log\log r)$.

Hardware Requirements

Breaking RSA-2048 requires factoring a 2048-bit integer. Analysis by Gidney and Ekerå (2021) estimates approximately:

  • 4,000 logical qubits (two $n$-qubit registers plus ancilla)
  • $\approx 10^8$ Toffoli gates in the modular exponentiation
  • Millions of physical qubits with current surface-code error rates ($\sim 10^{-3}$ per gate), since each logical qubit needs $O(d^2)$ physical qubits for a distance-$d$ code

The largest quantum computers as of 2025 have $O(10^3)$ physical qubits with error rates that are still too high for fault-tolerant operation at this scale. Cryptographically relevant Shor’s algorithm is likely a decade or more away.

Examples

Factoring $N = 15$, $a = 7$. The order of $7 \bmod 15$ is $r = 4$ since $7^1 = 7$, $7^2 = 49 \equiv 4$, $7^3 \equiv 28 \equiv 13$, $7^4 \equiv 91 \equiv 1 \pmod{15}$. Then $a^{r/2} = 7^2 = 49 \equiv 4 \pmod{15}$, and:

$$\gcd(4 - 1, 15) = \gcd(3, 15) = 3, \qquad \gcd(4 + 1, 15) = \gcd(5, 15) = 5$$

Factors found: $15 = 3 \times 5$. Demonstrated on IBM Quantum hardware (5-qubit device, 2016) for this and similar small instances.

Post-quantum cryptography. NIST standardised three post-quantum algorithms in 2024: CRYSTALS-Kyber (key encapsulation, lattice-based), CRYSTALS-Dilithium (signatures, lattice-based), and SPHINCS+ (signatures, hash-based). Their security relies on the hardness of lattice problems (shortest/closest vector problems) and hash preimage finding, neither of which has a known subexponential quantum algorithm.

Quantum volume benchmarking. IBM uses circuits equivalent to small instances of Shor-like algorithms as quantum volume benchmarks, since the required combination of all-to-all connectivity, gate fidelity, and circuit depth stresses every aspect of hardware quality.

Read Next: Fast Fourier Transform