Algorithms for Quantum Computation: Discrete Logarithms and Factoring
A quantum computer could factor huge numbers fast — and break the encryption that guards the internet.
In 1994 a mathematician proved that a machine no one had yet built could, in principle, crack the codes that keep the internet's secrets.
The big idea
Almost all secure communication online — your bank, your messages, your passwords — rests on a simple bet: that even the fastest computer would take longer than the age of the universe to find the two prime numbers that were multiplied together to make a certain huge number. Peter Shor showed that a quantum computer, a fundamentally different machine that obeys the rules of quantum physics, could win that bet quickly. It could factor those enormous numbers fast — and so unlock the codes built on them.
His trick was to turn factoring into a question about rhythm. Instead of hunting for the factors head-on, you look at a repeating pattern hidden in the numbers and find how often it repeats. A quantum computer can sense that repetition all at once, by letting many possibilities interfere like overlapping waves.
How it came about
Through the 1980s a few physicists — Richard Feynman among them — wondered whether a computer built from quantum parts could do things an ordinary one couldn't. The idea was intriguing but had no compelling use. Then in 1994, at AT&T's Bell Labs, Peter Shor found one. Building on a clever result by Daniel Simon about finding hidden periods, he showed a quantum machine could factor numbers and break the most widely used codes.
The talk he gave that November electrified the field. Overnight, quantum computing stopped being a curiosity and became a matter of national security; money and talented people poured in, and the long race to actually build such a machine — and to defend against it — began.
Why it mattered
RSA and its relatives guard almost every secure connection on Earth (RSA is in this Library). Shor's result was a proof — not a hunch — that a large enough quantum computer would break them. That single fact launched the worldwide hunt for 'post-quantum' codes that even a quantum computer cannot crack; in 2024 the first such standards were officially published, and the world's systems are now being upgraded — years before the threatening machine exists.
A way to picture it
Imagine a locked bell tower whose door opens only if you know exactly how many seconds pass between two particular chimes. A person with a stopwatch would have to listen for an impossibly long time to be sure of the rhythm. A quantum computer is like being able to hear every possible rhythm sounding together and instantly pick out the real one. Once it knows the beat, the door — and the secret behind it — simply opens.
Where it sits
This is the dark twin of the cryptography already in this Library. Diffie and Hellman (1976), and then RSA (1978), built public-key codes on problems thought to be hopelessly hard; Shor showed those problems are only hard for the machines we had. His work sits beside Turing's question of what computers can do at all, and points to a future where the security of everything — from money to Bitcoin, also here — may have to be rebuilt.
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems which are generally thought to be hard on a classical computer and which have been used as the basis of several proposed cryptosystems.