Shor's algorithm is a quantum algorithm that factors large integers in polynomial time. It was invented by Peter Shor in 1994 and is one of the most consequential results in quantum computing, because it would break the RSA public-key cryptosystem if run on a sufficiently large fault-tolerant quantum computer.

Classically, the best known factoring algorithm (the general number field sieve) runs in sub-exponential time $O(e^{O(n^{1/3}\log^{2/3} n)})$ for an $n$-bit integer. Shor's algorithm runs in polynomial time $O(n^3)$ on a quantum computer with $O(n)$ qubits, an exponential speedup.

Shor's algorithm reduces the factoring problem to the order-finding problem. Given $N$ to factor and a randomly chosen coprime $a$ (with $\gcd(a, N) = 1$), find the smallest $r$ such that $a^r \equiv 1 \pmod{N}$. If $r$ is even and $a^{r/2} \not\equiv -1 \pmod{N}$, then $\gcd(a^{r/2} \pm 1, N)$ yields a non-trivial factor of $N$ with probability at least $1/2$.

The quantum part of Shor's algorithm is order-finding via quantum phase estimation. First, prepare a uniform superposition over $x \in \{0, \ldots, 2^n-1\}$ and query the modular exponentiation function to get:

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

Measuring the second register collapses the first to a superposition of all $x$ giving the same remainder. Applying the inverse QFT then concentrates the probability at multiples of $2^n/r$, allowing $r$ to be recovered by continued fractions. The classical part then computes $\gcd(a^{r/2}\pm 1, N)$.