Algorithm Steps
1. Choose random a < N, gcd(a,N)=1
2. Find period r of f(x) = aˣ mod N
3. Quantum: QFT finds r in O(log²N)
4. If r even and aʳ/² ≠ −1 mod N:
5. p = gcd(aʳ/²+1, N)
6. q = gcd(aʳ/²−1, N)
Classical factoring: O(exp(n^(1/3)))
Shor's: O(n²log n log log n)
Why Quantum?
The QFT transforms the periodic sequence aˣ mod N into a superposition with peaks at multiples of N/r.
The periodicity is global — exponentially many values contribute simultaneously via quantum interference.
RSA encryption relies on factoring being hard classically. Shor's algorithm breaks RSA when large quantum computers are built (≥4000 error-corrected qubits for RSA-2048).