Shor's Algorithm: Period-Finding Visualizer

Number to Factor

N 15

Base a (coprime to N) 7

Live Readouts

True order r (a^r≡1 mod N)

—

Measured x₀ (2nd register)

—

Measured k (after QFT)

—

Estimated period r̃

—

Pick N and a, then run.

How it works

Shor's algorithm factors N by finding the period r of f(x) = aˣ mod N, where a is coprime to N. Once r is known, N usually factors via a classical gcd:

if r even and a^(r/2) ≠ -1 (mod N):
  p = gcd(a^(r/2) - 1, N)
  q = gcd(a^(r/2) + 1, N)
  N = p · q

The quantum part finds r exponentially faster than any known classical algorithm. A register is prepared in an equal superposition over x = 0…Q-1 (Q = 2ⁿ), f(x) is computed into a second register, and that second register is measured, yielding some value f(x₀). This collapses the first register onto the periodic set {x : x ≡ x₀ (mod r)} — exactly what "Collapse register" shows.

Applying the quantum Fourier transform to that periodic comb produces constructive interference at k ≈ multiples of Q/r and destructive interference elsewhere:

QFT amplitude:  A(k) = (1/√M) Σₓ e^(2πi k x / Q),  x over the collapsed set
Probability:    P(k) = |A(k)|²   →  peaks near j·Q/r  for j = 0…r-1

"Measure output register" samples one k from this real probability distribution, then runs the continued-fraction expansion of k/Q to recover a candidate period r̃ — the classical post-processing step every real Shor's-algorithm run performs after the quantum measurement.

N / a — the composite to factor and the random base; only bases coprime to N are offered.
Register qubits n — resolution of the frequency register; a larger Q gives sharper, better-resolved peaks.
Bars — the QFT probability distribution P(k); tall gold bars sit at the true multiples of Q/r, the measured outcome flashes cyan.

This is a full classical re-implementation of the algorithm's math (exact modular exponentiation, exact discrete Fourier sum, exact continued fractions) — the only thing simulated rather than run on real qubits is the exponential speed-up itself.

True period peaks (Q/r) QFT probability P(k) Measured outcome

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.