Introduction

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.

Find the Period

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 a1,a2,a3,…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">Factoring <b>N</b> becomes <b>period-finding</b>. Pick a base <b>a</b>, and look at the powers <code>a^1, a^2, a^3, …</code> taken <b>mod N</b>. The sequence repeats; the cycle length is the <b>period r</b>. From an even period, <code>gcd</code> pops out a factor. Reading the cycle is easy — finding r fast is the quantum part.</p>
<div class="row">
  <label>N = <select id="N"></select></label>
  <button id="rand" type="button">Pick random base a</button>
</div>
<div class="seq" id="seq"></div>
<div class="status" id="status">Choose N and pick a base a.</div>
<div class="btns">
  <button id="period" type="button">Find the period r</button>
  <button id="factor" type="button">Recover the factors</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Shor’s reduction: factoring N -> finding the PERIOD r of a^x mod N (the multiplicative order of a). Checking/reading the cycle is easy; the quantum Fourier transform is what finds r fast. Once r is known and even, the factors come from gcd(a^(r/2) ± 1, N). Classically here we just walk the sequence.
const SEMIPRIMES = [15, 21, 33, 35, 39, 51, 55];
function gcd(a, b){ while(b){ [a, b] = [b, a % b]; } return a; }
function modpow(base, exp, mod){ let r = 1; base %= mod;
  while(exp > 0){ if(exp & 1) r = (r * base) % mod; base = (base * base) % mod; exp >>= 1; } return r; }

let N = SEMIPRIMES[0], a = null, period = null;

const $ = id => document.getElementById(id);
const sel = $('N');
SEMIPRIMES.forEach(n => { const o = document.createElement('option'); o.value = n; o.textContent = n; sel.appendChild(o); });

function reset(){ a = null; period = null; $('seq').innerHTML = ''; $('out').textContent = '';
  $('factor').disabled = true; setStatus(`Pick a base a to begin.`, ''); }
function setStatus(t, c){ const s = $('status'); s.textContent = t; s.className = 'status ' + c; }

// Order/period r = smallest r>=1 with a^r mod N == 1. Only defined when gcd(a,N)==1.
function findPeriod(a, N){ let v = a % N, r = 1;
  while(v !== 1){ v = (v * a) % N; r++; if(r > N) return null; } return r; }

function renderSeq(highlightR){
  const box = $('seq'); box.innerHTML = '';
  if(a === null) return;
  const upto = highlightR ? highlightR : Math.min(8, N);
  for(let x = 1; x <= upto; x++){
    const val = modpow(a, x, N);
    const d = document.createElement('div');
    d.className = 'term' + (val === 1 ? ' one' : '');
    if(highlightR && x === highlightR) d.className = 'term repeat';
    d.textContent = a + '^' + x + '=' + val;
    box.appendChild(d);
  }
}

function pickRandom(){
  N = parseInt(sel.value, 10);
  // pick a in [2, N-1] coprime to N (so it has a well-defined period)
  let tries = 0;
  do { a = 2 + Math.floor(Math.random() * (N - 3)); tries++; }
  while(gcd(a, N) !== 1 && tries < 50);
  if(gcd(a, N) !== 1){ // lucky: shares a factor -> instant classical hit
    const f = gcd(a, N);
    period = null; renderSeq(null);
    setStatus(fmt(`Lucky! a=%a% shares a factor with N.`, { a: a }), 'ok');
    $('out').textContent = 'gcd(' + a + ', ' + N + ') = ' + f + '  ->  ' + N + ' = ' + f + ' x ' + (N / f);
    $('factor').disabled = true; return;
  }
  period = null; $('out').textContent = ''; $('factor').disabled = true;
  renderSeq(null);
  setStatus(fmt(`Base a = %a%. Now find its period.`, { a: a }), '');
}

function doPeriod(){
  if(a === null){ setStatus(`Pick a base a first.`, 'bad'); return; }
  period = findPeriod(a, N);
  if(!period){ setStatus(`No period found (try another base).`, 'bad'); return; }
  renderSeq(period);
  setStatus(fmt(`Found period r = %period%  (a^%period% mod N = 1).`, { period: period }), 'ok');
  $('factor').disabled = false;
}

function doFactor(){
  if(!period){ setStatus(`Find the period first.`, 'bad'); return; }
  if(period % 2 !== 0){ setStatus(`Period is odd — Shor retries with a new base.`, 'bad');
    $('out').textContent = fmt(`r = %period% is odd. Pick another base a and try again.`, { period: period }); return; }
  const half = modpow(a, period / 2, N);
  if(half === N - 1){ setStatus(`a^(r/2) = -1 mod N — degenerate, retry with new base.`, 'bad');
    $('out').textContent = fmt(`a^(r/2) mod N = %half% (= N-1). Pick another base a.`, { half: half }); return; }
  const f1 = gcd(half - 1, N), f2 = gcd(half + 1, N);
  const factors = [f1, f2].filter(f => f > 1 && f < N);
  if(factors.length){
    const p = factors[0], q = N / p;
    setStatus(fmt(`Factored! %N% = %p% x %q%`, { N: N, p: p, q: q }), 'ok');
    $('out').textContent =
      fmt(`r = %period% (even)
a^(r/2) mod N = %a%^%v% mod %N% = %half%
gcd(%half%-1, %N%) = %f1%,  gcd(%half%+1, %N%) = %f2%
=> %N% = %p% x %q%`, { period: period, a: a, v: period / 2, N: N, half: half, f1: f1, f2: f2, p: p, q: q });
    console.log(fmt(`Shor: N=%N% a=%a% r=%period% -> %p% x %q%`, { N: N, a: a, period: period, p: p, q: q }));
  } else {
    setStatus(`This base did not yield a factor — retry.`, 'bad');
    $('out').textContent = `gcd values gave no proper factor. Pick another base a.`;
  }
}

sel.addEventListener('change', () => { N = parseInt(sel.value, 10); reset(); });
$('rand').addEventListener('click', pickRandom);
$('period').addEventListener('click', doPeriod);
$('factor').addEventListener('click', doFactor);
reset();
Result
Console

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.

The Real Complexity

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 ax mod Na^{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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/shor-algorithm/Content licensed under CC BY-NC 4.0.