# Shor's algorithm
**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.

## Structure
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$.

## Quantum subroutine
The quantum part of Shor's algorithm is order-finding via [[qpe|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|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)$.