Multiplying two large primes together is easy; pulling the product apart again is the problem that a huge slice of modern cryptography is built on. RSA and Diffie–Hellman are secure precisely because nobody knows how to factor a several-hundred-digit number in any reasonable time on a classical machine — the best classical method, the number field sieve, still takes sub-exponential time. In 1994 Peter Shor found a quantum algorithm that factors in polynomial time. It was the moment quantum computing stopped being a curiosity and became a threat model.

The surprise is that the quantum part of Shor's algorithm has nothing directly to do with factoring. The quantum computer solves a completely different-looking problem — finding the order of a number modulo N — and a short chain of classical number theory turns that into a factor. This page follows the whole pipeline: the classical reduction that makes factoring a question about periods, the quantum core that reads a period off using phase estimation, and the continued-fraction step that decodes the answer.

Step 1 — the classical reduction: factoring becomes order-finding

Here is the trick that lets a quantum computer factor without ever "trying" a divisor. To factor N (odd, composite, not a prime power), pick a random a in the range 1 < a < N. Compute \gcd(a, N) with the Euclidean algorithm; on the wild chance it isn't 1 you have already stumbled onto a factor and are done. Otherwise a is coprime to N, so it has an order — the smallest r > 0 with

Suppose we can find that r. Rewrite the defining equation as a^{r} - 1 \equiv 0 \pmod N. If r is even, we can factor the left side as a difference of two squares:

So N divides the product \left(a^{r/2} - 1\right)\left(a^{r/2} + 1\right). Now the key observation: a^{r/2} \not\equiv 1 \pmod N automatically (else the order would be r/2, not r), so the first factor isn't a multiple of N. As long as the second also avoids being a multiple — that is, as long as a^{r/2} \not\equiv -1 \pmod N — then N's prime factors must be split between the two brackets. Compute

and each is a nontrivial factor of N. Two GCDs — cheap, classical, exact — turn a period into a factorisation.

The conditions, and when to retry

Two things had to go right: the order r must be even, and a^{r/2} must not be \equiv -1 \pmod N. Either can fail for an unlucky a — if r is odd there is no a^{r/2} to speak of, and if a^{r/2} \equiv -1 then \gcd(a^{r/2}+1, N) = N, a trivial factor that tells you nothing. In both cases you simply throw a away and draw a fresh random one.

This is not a fatal flaw, because the good a's are common. A theorem guarantees that for an odd N with at least two distinct prime factors, a randomly chosen coprime a gives a usable (even order, non--1) result with probability at least \tfrac12. So a handful of attempts almost certainly succeeds — Shor's algorithm is a randomised algorithm that may need a retry, not a machine that fails outright.

Worked example: factoring N = 15 with a = 7

Let's run the whole classical wrapper by hand on the textbook case N = 15. Draw a = 7; since \gcd(7, 15) = 1, it has an order. List the powers modulo 15 until we return to 1:

We first hit 1 at the fourth power, so the order is r = 4. Check the conditions: r = 4 is even (good), and a^{r/2} = 7^{2} \equiv 4, which is neither 1 nor -1 \equiv 14 \pmod{15} (good). Both conditions hold, so we're clear to extract factors from a^{r/2} \equiv 4:

And indeed 15 = 3 \times 5. The random choice a = 7, its order 4, and two GCDs handed us the full factorisation — no trial division ever tested "is 3 a factor?" The entire difficulty was compressed into finding the order r = 4, and that is the one step we now hand to the quantum computer.

Step 2 — the quantum core: order-finding is period-finding

Why is the order hard classically? Because r is the period of the function

which satisfies f(x + r) = f(x) — the sequence a^0, a^1, a^2, \dots marches through residues and then repeats with period exactly r. For a several-hundred-digit N that period can be astronomically large, and classically there's no shortcut to it. Finding the hidden period of a function is precisely the sort of global question a quantum computer is good at — this is Simon's periodicity idea, lifted from bit-strings to the integers.

The quantum handle is a unitary operator. Define U by how it acts on a residue |y\rangle:

Multiplying by a just permutes the residues coprime to N (it's invertible, since a has an inverse mod N), so U is a genuine unitary. And because applying it r times returns every residue to itself (a^{r} \equiv 1), the number r is baked into U's eigenvalues.

The eigenphases spell out s/r

The eigenvectors of U are the "period waves"

one for each s = 0, 1, \dots, r-1. The eigenvalue is e^{2\pi i \, s/r} — an eigenphase of exactly s/r. So the period r we're hunting for is sitting in the denominator of every eigenphase of U. And reading the phase of a unitary's eigenvalue is exactly what quantum phase estimation (QPE) does.

Two conveniences make this practical. First, we never have to prepare a specific |u_s\rangle (which would require knowing r already): the simple state |1\rangle is an equal superposition of all of them, |1\rangle = \tfrac{1}{\sqrt r}\sum_{s} |u_s\rangle, so feeding |1\rangle into QPE returns an estimate of s/r for a uniformly random s. Second, the controlled powers QPE needs, U^{2^{j}}, are just "multiply by a^{2^{j}} \bmod N" — modular exponentiation by repeated squaring, which is efficient. QPE hands back an estimate of the fraction s/r, accurate to enough bits to pin it down.

Step 3 — continued fractions recover r

QPE doesn't give us s/r as a clean fraction — it gives a binary estimate, some number very close to s/r but cluttered with trailing bits. We need to recognise which simple fraction it is approximating, and read off the denominator. That is exactly what continued fractions are for: the convergents of a real number are the best rational approximations with small denominators, so expanding the QPE estimate and taking the convergent whose denominator is below N recovers s/r in lowest terms.

Take a tiny example with r = 4 (as in the N = 15 case). Suppose s = 3, so the true phase is s/r = \tfrac34 = 0.75, and QPE with a few bits returns the estimate 0.7500\ldots. Expand it as a continued fraction:

The last convergent is \tfrac34: in lowest terms its denominator is 4, so we read off r = 4. (When \gcd(s, r) \neq 1 the denominator we recover is only a divisor of r — another reason the algorithm sometimes repeats: a quick check a^{r} \stackrel{?}{\equiv} 1 confirms the candidate, and a couple of runs, or taking the least common multiple of two candidate denominators, nails the true order.) With r in hand we fall straight back into the classical GCD step from before.

The whole pipeline at a glance

Step through the diagram to see how little of Shor's algorithm is actually quantum. Four of the five boxes are ordinary classical number theory; the quantum computer is called exactly once, for the order-finding step in the middle. Everything else — the random choice, the continued-fraction decoding, the GCDs — runs on your laptop.

This is the shape of almost every known quantum speed-up: a thin quantum kernel that exploits some hidden algebraic structure (here, periodicity), wrapped in classical pre- and post-processing. The quantum computer isn't "trying all divisors at once" — it is extracting one number, a period, that classical machines can't get at efficiently.

Why it matters: polynomial time, and the clock on RSA

Counting the cost: the modular exponentiations dominate, and with fast arithmetic the whole algorithm runs in roughly

quantum operations — polynomial in the number of digits of N. Compare the best classical factoriser, the general number field sieve, whose running time \exp\!\big(c\,(\log N)^{1/3}(\log\log N)^{2/3}\big) is sub-exponential but super-polynomial. That gap is the difference between "secure for the age of the universe" and "broken over a long weekend."

The consequence is stark. RSA's security rests on factoring being hard; Diffie–Hellman's rests on the closely related discrete logarithm, which Shor's technique also solves. A large enough, error-corrected quantum computer would therefore break the public-key cryptography that secures essentially all internet traffic. No such machine exists yet — today's devices are nowhere near the millions of clean qubits required — but the mere existence of the algorithm is why the world is already migrating to post-quantum cryptography: schemes based on problems (like lattices) that Shor's method does not crack.

Summary