Shor's Factoring

Factoring big numbers secures the internet — and Shor’s algorithm cracks it with an exponential speedup by turning factoring into finding a hidden rhythm.

Quantum Computing · Lesson 10 · 11 min read

Almost all internet privacy rests on one bet: multiplying two huge prime numbers is easy, but un-multiplying the result back into those primes (factoring) is practically impossible. For a big enough number a classical computer would grind for longer than the age of the universe. Shor’s algorithm lets a quantum computer do it in something like a coffee break. How can a quantum machine crack a problem classical ones can’t touch — and should you panic about your bank account? Hold the question.

Why factoring secures the internet

RSA encryption — the lock behind much of the web — relies on a one-way street. Multiplying two large primes to get a number N is trivial. Going backward, finding the primes from N alone, is believed to take classical computers time that grows exponentially with the size of N. That asymmetry is the lock: anyone can use N to encrypt, but only someone who knows its prime factors can decrypt. Break factoring and you break the lock.

Shor's insight: factoring hides a repeating rhythm

Shor’s leap was to turn factoring — which looks like a search for divisors — into a completely different question: finding the period of a repeating pattern. Take any number and look at its powers wrapped around by remainders (mod N); the sequence eventually repeats with some period r. A little ordinary math then converts r into the factors of N. The catch: for huge N that repeating sequence is astronomically long, so finding its period r is the hard part — and that is exactly what a quantum computer is shockingly good at.

Quantum period-finding: making the rhythm ring out

Here the L08 recipe pays off. Put all the positions into superposition, compute the repeating pattern across all of them at once, then apply the quantum Fourier transform — interference tuned so that everything except the true period cancels, and the period rings out when you measure. That step finds r in a number of operations that grows gently (polynomially), not exponentially — the headline exponential speedup. The honest caveat: it needs a large, error-corrected machine that does not exist yet, which is why today’s computers can’t factor big numbers — but it’s why the world is already moving to post-quantum cryptography (Module 5).

Factoring 15 by period-finding (small enough to follow by hand):
1. Goal: factor N = 15. Pick a random number with no factor in common with 15 — say a = 2.
2. List the remainders of its powers mod 15: 2¹=2, 2²=4, 2³=8, 2⁴=16→1, then 2, 4, 8, 1, … It repeats every 4 steps, so the period is r = 4.
3. Classical cleanup: compute a^(r/2) ± 1 = 2² ± 1 = 5 and 3. Then gcd(5, 15) = 5 and gcd(3, 15) = 3.
4. Factors found: 15 = 3 × 5.
5. The ONLY hard part for huge N is step 2 — the sequence is unimaginably long. Shor uses superposition plus the quantum Fourier transform to find the period r efficiently; everything else is quick classical math. So Shor = quantum period-finding + classical arithmetic → an exponential speedup over pure classical factoring.