Helpful context:

RSA encryption secures the internet. When your browser negotiates an HTTPS connection, it uses RSA or a related scheme to establish a shared secret. The security of RSA rests on a single assumption: that factoring large numbers is computationally hard.

A 2048-bit RSA number has roughly 620 decimal digits. The best known classical algorithm for factoring it - the General Number Field Sieve - would take longer than the age of the universe on any computer we could build or imagine. This is not a practical limitation; it is an astronomical gap.

In 1994, Peter Shor showed that a quantum computer could factor a 2048-bit number in hours. Every time you make a secure connection online, you are trusting that large-scale quantum computers do not yet exist.

Why Factoring Is Hard (Classically)

Given $N = p \cdot q$ where $p$ and $q$ are large primes, the multiplication is trivial - a few microseconds. Finding $p$ and $q$ from $N$ is a different matter entirely.

The best classical algorithm 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 2048-bit $N$, this is still a number so large that no feasible computation could evaluate it. RSA has been secure for over 40 years on this basis.

The Classical Reduction: Factoring to Period-Finding

Shor’s algorithm is mostly classical mathematics, with one quantum subroutine at its heart. The key insight is a number-theoretic reduction.

Pick a random integer $a$ with $1 < a < N$ and $\gcd(a, N) = 1$. Consider the sequence:

$$a^0 \bmod N, \quad a^1 \bmod N, \quad a^2 \bmod N, \quad a^3 \bmod N, \ldots$$

By Euler’s theorem, this sequence is eventually periodic. The order $r$ of $a$ modulo $N$ is the smallest positive integer satisfying:

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

Once you have $r$, you can factor $N$. Here’s why. From $a^r \equiv 1$:

$$(a^{r/2} - 1)(a^{r/2} + 1) \equiv 0 \pmod{N}$$

This means $N$ divides the product $(a^{r/2}-1)(a^{r/2}+1)$. If $r$ is even and $a^{r/2} \not\equiv -1 \pmod N$, then $\gcd(a^{r/2} - 1, N)$ and $\gcd(a^{r/2} + 1, N)$ each give a non-trivial factor of $N$.

Number theory guarantees this works for a random $a$ with probability at least $1/2$. Try a few random values of $a$, and you’ll factor $N$ with high probability.

The bottleneck: finding $r$. Classically, computing the order of $a$ modulo $N$ takes exponential time - it’s essentially as hard as factoring. This is where quantum computation enters.

The Quantum Part: Finding the Period

Define a function $f(x) = a^x \bmod N$. This function is periodic with period $r$ - the order of $a$ we want to find. Classically, to find $r$ you’d evaluate $f$ at many points and look for repetitions. With period $r$ potentially as large as $N$, this takes $O(N)$ time.

Quantum computers find periods efficiently through the Quantum Fourier Transform.

Prepare a superposition of all inputs:

$$\frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle|0\rangle$$

Apply the function $f$ as a quantum gate:

$$\frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle|f(x)\rangle = \frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle|a^x \bmod N\rangle$$

Measure the second register. This collapses the first register to a superposition over all $x$ values that produce the same $f(x)$ - that is, all $x$ in the same residue class modulo $r$. The state becomes a uniform superposition over the periodic lattice $\{x_0, x_0 + r, x_0 + 2r, \ldots\}$ for some offset $x_0$.

Apply the QFT to this periodic superposition.

The Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analogue of the classical Discrete Fourier Transform. On computational basis states:

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

The key property: the QFT of a periodic state peaks sharply at frequencies that are multiples of $M/r$. This is quantum interference at work - the amplitudes at non-multiples cancel out; the amplitudes at multiples reinforce.

After the QFT, measure the first register. You get a value close to $jM/r$ for a random integer $j$. Divide by $M$ to get a rational number close to $j/r$. Apply the continued fraction algorithm - a classical procedure - to find the fraction $j/r$ in lowest terms. The denominator gives $r$ (or a divisor of $r$, which you can extend with a few more measurements).

The entire QFT on $n$ qubits uses $O(n^2)$ gates - vastly more efficient than the classical FFT’s $O(n \cdot 2^n)$ operations. The classical FFT is polynomial in the number of elements $2^n$; the QFT is polynomial in $n$, the number of qubits.

The Full Algorithm

Putting it together:

  1. Pick random $a$ with $\gcd(a, N) = 1$.
  2. Prepare superposition: $\frac{1}{\sqrt{M}} \sum_{x=0}^{M-1} |x\rangle|0\rangle$
  3. Compute modular exponentiation in superposition: $\sum_x |x\rangle|a^x \bmod N\rangle$
  4. Measure second register (or skip - not strictly necessary).
  5. Apply inverse QFT to first register.
  6. Measure first register to get integer $\tilde{y} \approx jM/r$.
  7. Apply continued fraction algorithm to $\tilde{y}/M$ to recover $r$.
  8. Compute $\gcd(a^{r/2} \pm 1, N)$ to get factors.

The dominant cost is step 3: computing $a^x \bmod N$ for a superposition of $x$ values. This requires controlled modular multiplications, using $O(n)$ multiplications each costing $O(n^2)$ gates, giving $O(n^3)$ total quantum gates. The QFT in step 5 costs $O(n^2)$. Overall: $O(n^3)$ quantum gates, or $O((\log N)^3)$.

Compare to the best classical algorithm: sub-exponential. Shor’s algorithm achieves an exponential speedup.

A Small Example

Factor $N = 15$ with $a = 7$.

The order of $7 \bmod 15$: $7^1 = 7$, $7^2 = 49 \equiv 4$, $7^3 \equiv 28 \equiv 13$, $7^4 \equiv 91 \equiv 1 \pmod{15}$. So $r = 4$.

Since $r = 4$ is even and $7^2 = 49 \equiv 4 \not\equiv -1 \pmod{15}$, we compute:

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

Factors: $15 = 3 \times 5$. This small instance was demonstrated on a 5-qubit IBM Quantum device in 2016.

Discomfort check. Shor’s algorithm requires a large, error-corrected quantum computer. The biggest quantum computers today have around 1,000 noisy physical qubits. Factoring 2048-bit RSA needs about 4,000 logical qubits - each logical qubit requiring roughly 1,000 physical qubits for error correction. That’s 4 million physical qubits with error rates far below what current hardware achieves. So when is this actually a threat?

Best current estimates: 10 to 20 years before cryptographically relevant quantum computers exist. The uncertainty is large - it could be sooner if hardware progress accelerates, or later if engineering challenges prove harder than expected. For this reason, NIST finalized post-quantum cryptographic standards in 2024 (CRYSTALS-Kyber for key exchange, CRYSTALS-Dilithium for signatures). Migration is happening now, not because the threat is imminent, but because “harvest now, decrypt later” attacks - storing encrypted traffic today to decrypt when quantum computers arrive - mean migration can’t wait until the hardware exists.

Post-Quantum Cryptography

The post-quantum standards rely on mathematical problems that are believed hard even for quantum computers:

  • Lattice-based (CRYSTALS-Kyber, CRYSTALS-Dilithium): security rests on the Shortest Vector Problem and related lattice problems. No known quantum algorithm achieves a superpolynomial speedup.
  • Hash-based (SPHINCS+): security reduces to properties of the hash function. Grover’s algorithm provides a quadratic speedup on hash preimage search, so key sizes are doubled to compensate.
  • Code-based: security based on decoding random linear codes (no known quantum shortcut).

These schemes are harder to work with than RSA - larger key sizes, more computation - but the security foundations don’t rely on the hardness of factoring or discrete logarithm.

Summary

Component What it does Quantum speedup
Classical reduction Factoring $\to$ order-finding None (classical)
Modular exponentiation Encodes $f(x) = a^x \bmod N$ in superposition Exponential
Quantum Fourier Transform Extracts period from periodic superposition Exponential vs classical DFT on $2^n$ elements
Continued fractions Recovers $r$ from QFT measurement None (classical)
GCD computation Extracts factors from $r$ None (classical)
Full algorithm Factors $n$-bit $N$ $O(n^3)$ vs sub-exponential classical

Shor’s algorithm is a beautiful decomposition: a classical number-theoretic reduction makes factoring equivalent to period-finding; the quantum computer performs the period-finding using interference; classical post-processing extracts the answer. The quantum part is contained to one subroutine, but it’s the subroutine that makes the whole thing work.

The implications are not theoretical. RSA, Diffie-Hellman, and elliptic-curve cryptography - the cryptographic infrastructure of the internet - are all vulnerable to Shor’s algorithm. Migration to post-quantum standards is underway. The window is likely measured in decades, not years, but the clock is running.

Read next: