Shor's Algorithm: Factoring by Finding a Period

Factoring is hard, but period-finding is the real target

Multiply two large primes together and the product is easy to compute; go the other direction, and finding the two primes given only their product is, as far as anyone has proven, exponentially hard for a classical computer as the numbers grow. Peter Shor's 1994 algorithm does not attack factoring head-on. It makes a detour through a completely different-looking problem - finding the period of a periodic sequence - solves that exponentially faster on a quantum computer, and then finishes the job with ordinary classical arithmetic.

From factoring N to the period of a^x mod N

To factor an odd composite N (not a prime power), pick a random integer a between 1 and N with gcd(a, N) = 1. The sequence a¹ mod N, a² mod N, a³ mod N, ... is guaranteed to be periodic - it must eventually repeat, since there are only N possible remainders - and its period r is what number theory calls the multiplicative order of a modulo N:

a^x mod N  is periodic in x with some period r,   a^r ≡ 1 (mod N)

if r is EVEN and a^(r/2) ≢ -1 (mod N):
    p = gcd( a^(r/2) - 1 ,  N )
    q = gcd( a^(r/2) + 1 ,  N )
    with high probability, p and q are non-trivial factors of N

The algebra behind that last step is ordinary: if r is even, a^(r/2) is a nontrivial square root of 1 modulo N, and N | (a^(r/2)-1)(a^(r/2)+1) without N dividing either factor alone - which the Euclidean algorithm's gcd computation exposes directly, in polynomial time, once r is known. About half of randomly chosen a values give a usable r on the first try, and re-rolling a different a when they don't is cheap, so the whole factoring problem really does reduce to one question: find r fast.

Why classical period-finding is stuck

Finding r classically means computing a^x mod N for enough values of x to spot the repeat - and for an n-bit N, r can be exponentially large in n, so a brute-force search is hopeless. No known classical algorithm finds r faster than sub-exponential time (the general number field sieve attacks factoring directly, with similar sub-exponential cost), which is precisely the gap Shor's algorithm exploits by moving the search into a quantum register that can represent every value of x at once.

The quantum part: superposition, then a transform

1. load register 1 with an equal superposition over x = 0 .. 2^t - 1
2. compute a^x mod N into register 2 (entangling the two registers)
3. apply the Quantum Fourier Transform to register 1
4. measure register 1 → result is close to a multiple of 2^t / r
5. classical continued-fraction expansion of (result / 2^t) reveals r

Step 2 puts the whole periodic function a^x mod N into superposition in a single pass, using modular exponentiation built from reversible arithmetic circuits. Because that function repeats with period r, register 1's amplitude pattern - after entangling with register 2 - inherits the same periodicity. The Quantum Fourier Transform (see our companion article on the QFT) is exactly the tool built to turn periodicity in one basis into sharp peaks in another: it concentrates measurement probability onto outcomes close to integer multiples of 2^t/r, and continued fractions - a purely classical, centuries-old technique - extract the exact fraction 2^t/r, hence r, from that single noisy measurement with high probability. If the attempt fails (r turns out odd, or gives a trivial factor), the whole thing is simply repeated with a fresh random a - a small constant number of tries suffices on average.

Why RSA cares

RSA encryption's security is a direct bet that factoring the product of two large primes is classically intractable. Shor's algorithm runs in time polynomial in the number of bits of N - a few thousand quantum gates on a few thousand logical, error-corrected qubits for a 2048-bit RSA key, by current estimates - which would make that bet fail outright. Building a quantum computer with enough clean, error-corrected qubits to run Shor's algorithm on cryptographically relevant numbers remains a hard engineering problem, not yet solved as of today, but the algorithm's existence is precisely why the cryptographic community has spent the last decade standardizing post-quantum algorithms - schemes based on lattice problems and other structures believed to resist both classical and quantum attack - to replace RSA and elliptic-curve cryptography before a sufficiently capable quantum computer arrives.

Frequently asked questions

Try it live

Everything above runs in your browser - open Shor's Algorithm and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.