⚛️ Shor's Algorithm

N (number to factor) Base a 2

Presets

N = 15

N = 21

N = 35

N = 91

1. Pick base a, check gcd(a,N)

2. Compute aˣ mod N sequence

3. Find period r (QFT peaks)

4. gcd(a^(r/2)±1, N) → factors

Chosen a—

gcd(a, N)—

Period r—

QFT peaks at—

a^(r/2) mod N—

gcd results—

Factors found—

To factor N, pick a<N coprime to N and find the period r of f(x)=aˣ mod N — the only step needing a quantum computer (period finding via the QFT). After QFT the register peaks at multiples of Q/r. If r is even and a^(r/2) ≢ −1, then gcd(a^(r/2)±1, N) yields nontrivial factors. Classical cost ~exp(n^⅓); Shor ~O(n³) — exponentially faster.