Shor's Algorithm, Honestly

Shor's algorithm factors large numbers by converting factoring into period finding, a job the quantum Fourier transform does efficiently. The mathematics is proved theory, but every hardware demonstration so far (such as 15 = 3 × 5) has been a compiled special case, and published engineering estimates put RSA-2048 at millions of physical qubits running for hours — far beyond any machine that exists today.

Why does factoring matter?

Multiply 3 by 5 and you get 15 instantly. Go the other way — given 15, find the two numbers that multiply to make it — and you have factoring. For small numbers it is trivial. For a 617-digit number (the size used in RSA-2048 encryption), no known classical algorithm finishes in any useful amount of time: the best one, the general number field sieve, still scales worse than any polynomial in the number of digits. Much of internet security rests on that difficulty — RSA encryption is safe exactly as long as factoring its public key stays impractical.

In 1994 Peter Shor proved that a sufficiently large quantum computer could factor an n-digit number in a time that grows only polynomially with n. That is a genuine exponential improvement over the best known classical method, and it is proved theory — the algorithm is correct, full stop. What is not settled is engineering: nobody has a machine remotely close to running it at cryptographic scale. This chapter walks through how the algorithm works, runs its quantum heart on a small circuit whose output you can predict exactly, and then gives you the honest numbers on how far away RSA-2048 really is. (The same algorithm also breaks the elliptic-curve signatures used by Bitcoin — same math, same distance.)