Quantum Computing · Instrument 09 · Shor's Algorithm

Shor's Algorithm — factoring by finding a rhythm

Factoring is hard; finding the period of a repeating sequence is the same problem in disguise. Shor's trick is to evaluate aˣ mod N for every x at once and let the quantum Fourier transform turn that hidden period into sharp peaks you can simply read off. This is the threat that RSA is racing — and the engine is the same interference you met in the algorithm theater, now buying an exponential speedup.

1 · the sequence aˣ mod N repeats — but its period is hidden

2 · the quantum register collapses to a comb — spikes every r, at a random offset

One measurement of this would give a single useless x. The period lives in the spacing, not any one spike — so we transform it instead of reading it.

3 · the QFT turns "spacing r in x" into peaks at multiples of Q/r

Period-finding readout

Recover the factors (classical)

N = ? × ?

Measure the spectrum to extract the period, then Euclid does the rest.

Why it's the threat — and what answers it