Home▸Quantum Computing▸Shor's Algorithm — Quantum Factoring via Period Finding

🔢 Shor's Algorithm — Quantum Factoring via Period Finding

Interactive Shor's algorithm simulator: find the period r of a^x mod N, view an illustrative quantum-spectrum visualization, and extract N's prime factors via the Euclidean algorithm.

Quantum Computing2DAdvanced60 FPS

About Shor's Algorithm

Shor's algorithm, published by mathematician Peter Shor in 1994, is the result that turned quantum computing from a theoretical curiosity into an existential question for modern cryptography. It factors a composite integer N by finding the period r of the sequence ȧ mod N for some base a coprime to N — a task a quantum computer can perform exponentially faster than any known classical method, using an operation called quantum phase estimation (QPE) to read off r directly from interference patterns in a superposition of states. Once r is known, a short calculation with the Euclidean algorithm, applied to a^r/2 ± 1 and N, very often reveals two genuine, nontrivial factors of N.

This matters far beyond pure mathematics: the RSA public-key cryptosystem, which still secures a large share of internet traffic, banking and secure communications, relies entirely on the assumption that factoring large numbers is computationally infeasible. A sufficiently large, fault-tolerant quantum computer running Shor's algorithm would break that assumption, which is precisely why governments and standards bodies are already rolling out post-quantum cryptography designed to resist quantum attacks. This simulator walks through the classical period-finding sequence, an illustrative recreation of the quantum spectrum QPE would measure, and the real Euclidean-algorithm arithmetic that turns a period into a factorization — using the small, hand-checkable examples N = 15, 21 and 35.

Frequently Asked Questions

What problem does Shor's algorithm actually solve?

It factors a composite integer N into its prime factors. Classically, the best known algorithms for factoring large numbers take time that grows almost exponentially with the number of digits, which is why RSA encryption, based on the difficulty of factoring, has remained secure for decades. Shor's algorithm factors N in time that grows only polynomially, an exponential speed-up for large enough N.

Why does finding a period r help factor N?

If a is coprime to N and r is even with a^r/2 not congruent to −1 modulo N, then a^r/2 − 1 and a^r/2 + 1 are witnesses that N divides their product but not either factor alone. The Euclidean algorithm applied to gcd(a^r/2 − 1, N) and gcd(a^r/2 + 1, N) then extracts a genuine nontrivial factor of N directly from that arithmetic fact.

Does this simulator run a real quantum computation?

No, and this page says so plainly. Simulating the actual quantum phase-estimation circuit that finds r would require modelling many qubits, which is far beyond what a browser canvas can usefully show. Instead, this demo computes r classically with an ordinary loop, then draws an illustrative "spectrum" with peaks at k/r to represent, for teaching purposes, what a real QPE measurement would look like.

Why does the period-finding trick sometimes fail?

The gcd construction only works when the period r is even and a^r/2 is not congruent to −1 modulo N. If r turns out odd, or if the gcd calculation only returns the trivial factors 1 or N, the chosen base a simply does not work for this method. The standard fix, both here and in the real algorithm, is to try a different random base a and repeat.

⚙ Under the hood

Interactive Shor's algorithm simulator: find the period r of a^x mod N, view an illustrative quantum-spectrum visualization, and extract N's prime factors via the Euclidean algorithm.

Quantum ComputingNumber TheoryCryptographyCanvas 2DPeriod Finding

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install