Shor's Algorithm

Every time you see the little padlock in your browser, you are trusting a strange asymmetry. A computer can multiply two enormous prime numbers together in a blink. But hand it the product and ask it to find those two primes again, and the fastest known classical methods would run for longer than the age of the universe on a number a few hundred digits long.

That one-way street is the heart of RSA, the encryption that protects bank logins, messages and software updates. Multiplying is the easy direction; factoring is the hard one, and the whole edifice assumes no one can do it quickly.

In 1994 a mathematician named Peter Shor found a crack. Not in the math of RSA itself, but in the machine: he showed that a quantum computer could factor large numbers efficiently — turning the universe-melting problem into an afternoon's work. The lock isn't broken yet, but the key now exists on paper.

Shor's real magic is a reduction: factoring a number N becomes finding the period of a simple repeating sequence. Pick a random base a and look at the powers $a^{1}, a^{2}, a^{3}, …$ all taken mod N. This sequence always eventually repeats, and the length of that cycle — the period r — almost always hands you a factor of N.

<p class="hint">{{hint}}</p>
<div class="row">
  <label>N = <select id="N"></select></label>
  <button id="rand" type="button">{{btn_rand}}</button>
</div>
<div class="seq" id="seq"></div>
<div class="status" id="status">{{status_choose}}</div>
<div class="btns">
  <button id="period" type="button">{{btn_period}}</button>
  <button id="factor" type="button">{{btn_factor}}</button>
</div>
<div class="out" id="out"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
code { background: #eef2f6; padding: .05rem .3rem; border-radius: 4px; font-size: .92em; }
.row { display: flex; gap: .7rem; align-items: center; flex-wrap: wrap; margin: .3rem 0 .6rem; }
label { font-size: .92rem; font-weight: 600; }
select { font: 600 14px system-ui, sans-serif; padding: .25rem .4rem; border-radius: 6px; border: 1px solid #adb1b8; }
.seq { display: flex; flex-wrap: wrap; gap: 5px; margin: .4rem 0; min-height: 44px; }
.term { padding: .35rem .5rem; border-radius: 8px; font: 700 13px ui-monospace, monospace;
        background: #e8eef3; color: #1d3557; border: 1px solid #cdd9e3; }
.term.one { background: #1d3557; color: #fff; border-color: #14233b; }
.term.repeat { background: #c9f0d4; color: #0a7d33; border-color: #8fd9a6; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.out { font: 600 13px ui-monospace, monospace; color: #1d3557; margin-top: .6rem; white-space: pre-wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button:disabled { opacity: .5; cursor: not-allowed; }
#rand { background: #fff; color: #1d3557; }

// Code not found

Try it below. Watching the sequence cycle is easy — you just read off when it returns to 1. But notice: classically you might have to step through a vast number of terms before the pattern reveals itself. Shor's quantum step finds that period all at once using the quantum Fourier transform, sidestepping the slow march. Once you have r, a little ordinary arithmetic with gcd pops out the primes.

So how hard is factoring, really — and what does Shor change?

• Classically, the best known algorithm (the general number field sieve) runs in sub-exponential but super-polynomial time. Double the key length and the work explodes; that is exactly why 2048-bit RSA keys are considered safe today.
• Verifying a factorization is trivial: multiply the factors back and check. That easy-to-check / hard-to-find gap is the signature of problems near P vs NP — though factoring is not believed to be NP-complete.
• Shor's algorithm (Peter Shor, 1994) runs in roughly O((log N)² · log log N) quantum operations — polynomial in the number of digits. This places FACTORING inside BQP, the class of problems a quantum computer can solve efficiently.
• The engine is the quantum Fourier transform. The slow part of factoring is finding the period r of $a^{x} \bmod N$; classically that hides among exponentially many values. The QFT computes the period of a superposition over all inputs at once, then makes r the overwhelmingly likely measurement outcome.

The punchline: Shor doesn't prove factoring is easy in general — it proves it is easy for a quantum computer. It is the headline reason anyone is building one, and the reason cryptographers are already racing to replace RSA.

Shor's algorithm is not an academic curiosity — it is a countdown clock under modern cryptography:

• RSA and the discrete log: the same period-finding trick also cracks the discrete logarithm, which means Diffie-Hellman key exchange and elliptic-curve cryptography (ECC) fall too. Almost all of today's public-key crypto rests on one of these.
• "Harvest now, decrypt later": adversaries can record encrypted traffic today and decrypt it once a large enough quantum computer exists. Long-lived secrets are already at risk.
• Post-quantum cryptography: in 2024 NIST standardized new algorithms (lattice-based schemes like ML-KEM) that resist both classical and quantum attacks. The global migration is underway.
• A reason to build quantum machines: factoring a militarily useful key would need millions of high-quality qubits — far beyond today's hardware — but Shor turned "why build a quantum computer?" into an obvious answer.

The same hardness that protects you, explored elsewhere through factoring and the discrete logarithm, is precisely what Shor's algorithm dissolves.

Shor's algorithm is a rare thing: a single idea that redrew the map of what is computationally hard. By reducing factoring to finding a hidden period, and then finding that period with the quantum Fourier transform, it pulled one of cryptography's load-bearing problems from "practically impossible" down to "polynomial time" — for a machine we are still learning to build.

The lesson lingers even before the hardware arrives. "Hard" is never absolute; it is always hard for a given model of computation. Change the machine and the whole landscape shifts. Whether you meet it through P vs NP or the discrete logarithm, the same humbling truth holds: today's unbreakable lock may simply be waiting for tomorrow's key.