Shor's algorithm

In plain terms

Here is the problem. Multiply two large primes: instant. Recover the primes from the product: with the best classical methods, effectively forever once the numbers are big enough. That one-way-street is not a theorem, but it is the working assumption -- and most public-key cryptography protecting the internet leans on it.

Shor's 1994 algorithm breaks the street. A quantum computer can factor in polynomial time. The route is indirect and elegant: factoring reduces, by classical number theory, to finding the period of a repeating sequence -- and period-finding is exactly what quantum interference does well. Load all values in superposition, apply the quantum Fourier transform, and the period stands out like a struck bell.

Sufficiently large machines do not exist yet. The mortgage on current cryptography has, nonetheless, been signed.

In CSD

The most demanding of the corpus's algorithm witnesses, and the disclaimer is standing: witnesses mark scope, they do not support foundations. What makes this one heavy is the plumbing -- the reversible modular arithmetic beneath the algorithm is built and verified in full, adders and multipliers and all, because that is where a formalisation either survives or quietly cheats.

The corpus makes no cryptographic claims, and the cost-model work bearing on real machines was deliberately extracted to a separate repository. What remains here is the existence proof: the formalised dynamics carries a complete, real algorithm end to end.

Mathematically

Quantum order-finding extracts the period of modular exponentiation in polynomial time via the quantum Fourier transform; a classical reduction, essentially Legendre-era number theory, converts the period into a factor with high probability. The quantum content is entirely the period-finding; the corpus's labour is mostly the verified reversible arithmetic underneath it.

The name

Peter Shor, born 1959, was an Olympiad medalist, took degrees at Caltech and MIT, and was at Bell Labs when he announced the algorithm in 1994. The community's reaction was unusually theatrical: word spread from a small talk before the paper existed, and within weeks half of physics had opinions about a result almost nobody had read.

The objection came instantly -- decoherence would kill any real machine -- and Shor answered it himself in 1995 with the first quantum error-correcting code, dispatching the counterargument to his own revolution. He moved to MIT in 2003. Few people have built both a field's central promise and its central defence.