⚛️ Shor's Algorithm

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.