This simulation walks through Shor's algorithm one stage at a time for small numbers you could never crack this way with a real quantum computer, but can watch step by step here: pick a base a coprime to N, compute the sequence aˣ mod N, find its period r (the one step a real quantum computer accelerates via the QFT), then take gcd(a^(r/2)±1, N) to pull out N's prime factors. Try different values of N and a to see when the method works cleanly and when it needs a retry.
A bar chart of aˣ mod N revealing the repeating period r, and a simulated quantum register showing probability peaks concentrated at multiples of Q/r after the quantum Fourier transform — the measurement outcome that lets you extract r.
Pick N to factor and a base a, or click Random a to auto-select one likely to succeed, then step through the four stages with Next stage or watch them all with Run all stages, or jump to a preset (N=15, 21, 35, 91) to see gcd, period r, QFT peaks and the final factors.
Shor's algorithm doesn't factor N directly — its only genuinely quantum step is finding the period r of aˣ mod N exponentially faster than any known classical method; everything else (picking a, computing the gcd) is ordinary classical arithmetic, which is exactly why it threatens RSA encryption.
It's the smallest positive integer r such that aʳ mod N = 1. Because aˣ mod N cycles with period r, once you know r you can use it to extract factors of N algebraically — this simulation highlights that repeating cycle directly in the bar chart.
Finding the period of aˣ mod N classically requires checking values one by one, which becomes exponentially slow for large N. A quantum computer can prepare a superposition over all x at once and use the QFT to make measurement outcomes concentrate at multiples of Q/r, revealing r in far fewer steps.
If the period r turns out to be odd, or if a^(r/2) ≡ −1 (mod N), the gcd step can't extract a nontrivial factor from that particular choice of a — the fix is simply to pick a different base a and try again, which is why the "Random a" button searches for one likely to work.
RSA's security relies on it being computationally infeasible to factor the large product of two primes used as its public key. Shor's algorithm factors integers exponentially faster than the best known classical algorithms, so a sufficiently large quantum computer running it could break RSA keys that are currently secure.
Once r is even and a^(r/2) isn't ≡ −1 mod N, the identity (a^(r/2)−1)(a^(r/2)+1) ≡ 0 (mod N) means N must share a nontrivial common factor with at least one of those two terms — computing the gcd against each pulls that shared factor straight out.