Shor's Factoring Algorithm

Shor's algorithm factors integers in polynomial time using quantum period finding via the Quantum Fourier Transform — exponentially faster than the best known classical algorithms.

Modular Exponentiation: f(x) = aˣ mod N

QFT Output — Period Detection

Algorithm State

Results

Choose N and a, then run.

Algorithm

1. Choose a coprime to N (gcd(a,N)=1)
2. Quantum: find period r of f(x)=aˣ mod N
3. If r even and aʳ/²≢-1 (mod N):
p = gcd(aʳ/²+1, N), q = gcd(aʳ/²-1, N)
Complexity: O((log N)³) vs classical O(exp(∛log N))

RSA security rests on the hardness of factoring. A 4000-qubit fault-tolerant quantum computer could factor 2048-bit RSA keys. Current record: Shor's on small numbers with real hardware.