Factoring by finding a period

Multiplying two primes of three hundred digits takes a computer microseconds. Undoing the product, recovering the primes from the result, would take the best known classical algorithms longer than the age of the universe. On that asymmetry rests RSA (Rivest, Shamir and Adleman, 1977), the cryptosystem that protects a large share of the world's communications. In 1994 Peter Shor, at Bell Labs, showed that a large enough quantum computer would break it.

§A little number theory

We work modulo $N$: two integers are congruent, $a\equiv b(\mathrm{mod}N)$, if $N$ divides $a-b$. The numbers coprime to $N$ form a group under multiplication, ${\mathbb{Z}}_N^{\ast }$, with $\phi (N)$ elements ($\phi$ is Euler's totient function).

RSA uses $N=pq$ and, with $\phi (N)=(p-1)(q-1)$, chooses an encryption exponent $e$ and a decryption exponent $d$ with $ed\equiv 1(\mathrm{mod}\phi (N))$. Knowing $p$ and $q$ makes $d$ easy to compute; without them, nobody knows how to do it efficiently. The best classical factoring algorithm, the general number field sieve, takes time about

sub-exponential but enormous: factoring the 829-bit number RSA-250 in 2020 took about 2,700 core-years of computation.

§From factoring to periods

The first idea of Shor's algorithm is classical, and goes back to Gary Miller (1976): if we know how to compute orders, we know how to factor.

Why the gcd works

Since $a^r\equiv 1$, $N$ divides $a^r-1=(a^{r/2}-1)(a^{r/2}+1)$. It does not divide the first factor, because $r$ is the smallest exponent with $a^r\equiv 1$; nor the second, by assumption. So $N$ shares a non-trivial factor with each of them, which Euclid's algorithm finds in polynomial time. The probability bound comes from the Chinese remainder theorem: the orders of $a$ modulo each prime power behave independently.

Everything comes down to finding the period $r$ of $f(x)=a^{x}modN$. Classically this is as hard as factoring. Quantumly, it is a job for the Fourier transform.

§Quantum order finding

1. Prepare two registers and put the first, of $t$ qubits with $N^2\le Q=2^t<2N^2$, in a uniform superposition: $\frac{1}{\sqrt{Q}}\sum _{x=0}^{Q-1}|x⟩|0⟩$.
2. Compute $f$ reversibly in the second register: $\frac{1}{\sqrt{Q}}\sum _x|x⟩|a^{x}modN⟩$. Modular exponentiation is done by repeated squaring, with $O(n^3)$ gates for $n$-bit numbers; it is the most expensive part of the algorithm.
3. Measure the second register (or just forget it). The first one collapses to a state that is uniform over an arithmetic progression $x_0,x_0+r,x_0+2r,\dots$: a periodic state of period $r$.
4. Apply the QFT to the first register and measure. The result $y$ is, with high probability, close to a multiple of $Q/r$: $|\frac{y}{Q}-\frac{\ell }{r}|\le \frac{1}{2Q}$ for some $\ell$.

The last step is to recover $r$ from the fraction $y/Q$, a problem of number theory more than two thousand years old: approximating a number by fractions with small denominators.

Since $\frac{1}{2Q}\le \frac{1}{2N^2}<\frac{1}{2r^2}$, the fraction $\ell /r$ (in lowest terms) appears among the convergents of $y/Q$, which can be computed with Euclid's algorithm. If $\ell$ and $r$ happen to be coprime, which happens with probability $\mathrm{\Omega }(1/\log \log r)$, the denominator is the order $r$. A few repetitions are enough.

§How far away is it?

In 2001 an IBM team factored $15=3\times 5$ with seven nuclear spins in a molecule. Since then the record of honest implementations has barely moved: Shor's algorithm needs many high-quality qubits and very long circuits, which means error correction. The estimates of resources needed for RSA-2048 have been falling: about 20 million physical qubits for 8 hours (Gidney and Ekerå, 2019), and less than a million noisy qubits in under a week (Gidney, 2025). Today's processors have on the order of a hundred to a thousand.

The threat is taken seriously, because encrypted data can be stored today and decrypted in the future. In 2024 NIST published the first post-quantum cryptography standards (FIPS 203, 204 and 205), based on problems over lattices and hash functions for which no efficient quantum algorithm is known. The mathematical lesson of Shor's algorithm goes beyond cryptography: quantum computers are extraordinarily good at finding hidden periodic structure in abelian groups (the hidden subgroup problem), and nobody knows whether that power extends much further.

§References

1. R. L. Rivest, A. Shamir and L. Adleman (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”. Communications of the ACM, 21(2).
2. G. L. Miller (1976). “Riemann's Hypothesis and Tests for Primality”. Journal of Computer and System Sciences, 13(3).
3. P. W. Shor (1994). “Algorithms for quantum computation: discrete logarithms and factoring”. FOCS (journal version: SIAM J. Computing, 1997).
4. L. M. K. Vandersypen et al. (2001). “Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance”. Nature, 414.
5. C. Gidney and M. Ekerå (2021). “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”. Quantum, 5 (arXiv 2019).
6. C. Gidney (2025). “How to factor 2048 bit RSA integers with less than a million noisy qubits”. arXiv preprint.
7. NIST (2024). FIPS 203, 204 and 205: post-quantum cryptography standards.