Shor's Algorithm (2D) — Period Finding & Factoring

N (number to factor) Base a (coprime to N)

N—

a—

gcd(a, N)—

Period r—

a^(r/2) mod N—

gcd(a^(r/2)-1, N)—

gcd(a^(r/2)+1, N)—

Factors found—

Real period-finding: computes the actual sequence f(x) = aˣ mod N and scans it for the smallest r with aʳ ≡ 1 (mod N) — the classical-simulable core of Shor's algorithm for small N. Then gcd(a^(r/2)±1, N) is the real classical post-processing step that extracts prime factors when r is even and a^(r/2) ≢ −1.

Pick N and a, then press "Compute period r".