Shor's Algorithm
The algorithm that put quantum computing on the map, by breaking RSA's core assumption
By the end of this topic you'll be able to
Factoring a large number N into its prime factors is widely believed to be hard for classical computers: the best known classical algorithm, the general number field sieve, runs in time that is sub-exponential but still explosive in the number of digits of N. RSA encryption's security rests entirely on this presumed hardness holding up.
Shor's algorithm, published by Peter Shor in 1994, factors N in time polynomial in the number of digits, given access to a quantum computer — the single result most responsible for governments and companies treating quantum computing as a serious strategic matter rather than a physics curiosity.
The key mathematical reduction is this: factoring N can be reduced to order-finding — given some integer a coprime to N, find the smallest positive integer r such that aʳ mod N = 1.
Once r is known (assuming it is even and aʳ/² is not congruent to −1 mod N, which happens often enough in practice), computing gcd(aʳ/²−1, N) and gcd(aʳ/²+1, N) yields nontrivial factors of N using nothing more than classical arithmetic — specifically, Euclid's algorithm. All of the genuinely quantum work is spent finding r; everything after that is classical post-processing.
Order-finding is exactly a phase estimation problem in disguise: define the unitary U|x⟩ = |ax mod N⟩. Its eigenvalues encode r directly, taking the form e^{2πik/r} for integer k, so running phase estimation with this particular U is precisely what's needed.
Measuring the resulting phase and post-processing it with the classical continued-fractions algorithm recovers r efficiently. Order-finding via phase estimation, followed by a classical gcd computation, together give a full factoring algorithm running in time polynomial in log(N) — an exponential speedup over the best known classical approach.
Two qualifications are worth being precise about. First, Shor's algorithm needs a fault-tolerant quantum computer capable of running a genuinely long circuit reliably; factoring numbers of cryptographically relevant size (thousands of bits) remains well beyond any hardware that exists today, which is why RSA has not in fact been broken in practice.
Second, Shor's algorithm does not threaten cryptography in general — it specifically breaks schemes whose security rests on factoring or the discrete logarithm problem, such as RSA, Diffie-Hellman, and elliptic-curve cryptography. This is precisely why post-quantum cryptography, built on different mathematical problems believed to resist quantum attack, has become an active and well-funded research area.
Try It Yourself
Factor N = 15, given that (quantum) order-finding has already determined the order of a = 7 modulo 15 is r = 4 (that is, 7⁴ mod 15 = 1, and no smaller positive power of 7 equals 1 mod 15).
- 1Check r is even: r = 4 is even. ✓ (required for the next step to make sense)
- 2Compute a^{r/2} mod N = 7² mod 15 = 49 mod 15 = 4.
- 3Check 4 is not ≡ −1 (i.e., not 14) mod 15 — confirmed, so this run of the reduction will produce a genuinely useful answer (if it had come out to 14, you'd need to rerun order-finding with a different random a).
- 4Compute gcd(a^{r/2} − 1, N) = gcd(4−1, 15) = gcd(3, 15) = 3, using Euclid's algorithm.
- 5Compute gcd(a^{r/2} + 1, N) = gcd(4+1, 15) = gcd(5, 15) = 5.
The factors are 3 and 5 (15 = 3×5) — found entirely by classical arithmetic (gcd via Euclid's algorithm) once the quantum part of the algorithm (order-finding) supplied r = 4.
Reference
| Order-finding | The subroutine Shor's algorithm actually solves quantumly | |
| Factor recovery | Classical post-processing once r is known | |
| Classical cost | Best known classical factoring (general number field sieve) | |
| Quantum cost | Shor's algorithm's runtime |
Quick Check
What quantum subroutine does Shor's algorithm rely on to find the order r?
Which cryptographic schemes does Shor's algorithm actually threaten?