Shor's algorithm factors large integers exponentially faster than any known classical method by finding the period r of the function aˣ mod N for a random base a coprime to N. A quantum computer finds that period using quantum phase estimation (QPE), then a short classical calculation with the Euclidean algorithm turns r into actual factors of N. Because RSA and similar public-key cryptosystems rely on factoring being hard, a large enough quantum computer running this algorithm would break them — which is exactly why post-quantum cryptography is being standardised today.
Honesty note: simulating a real QPE circuit needs many qubits and is far too heavy for a browser canvas. This demo shows the classical period-finding sequence exactly, then draws a simplified, illustrative "spectrum" with peaks at the phases k/r that a real quantum measurement would produce — it is a teaching aid, not a simulated quantum circuit.
aʳ ≡ 1 (mod N) — r is the multiplicative order of a
modulo N. When r is even and a^(r/2) ≢ −1 (mod N),
gcd(a^(r/2) − 1, N) and
gcd(a^(r/2) + 1, N) are nontrivial factors of N.
Peter Shor published this algorithm in 1994, showing for the first time that quantum computers could solve a practically important problem exponentially faster than any known classical algorithm. Small-scale demonstrations — factoring numbers like 15 and 21 — have been carried out on real physical quantum-computing hardware since the early 2000s, though scaling up to cryptographically relevant sizes remains a major engineering challenge.
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 ȧ 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 ar/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.
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.
If a is coprime to N and r is even with ar/2 not congruent to −1 modulo N, then ar/2 − 1 and ar/2 + 1 are witnesses that N divides their product but not either factor alone. The Euclidean algorithm applied to gcd(ar/2 − 1, N) and gcd(ar/2 + 1, N) then extracts a genuine nontrivial factor of N directly from that arithmetic fact.
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.
The gcd construction only works when the period r is even and ar/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.