Shor's Algorithm, Honestly
Shor's algorithm factors large numbers by turning factoring into period finding. Period finding means finding how often a pattern repeats, and the quantum Fourier transform does that job well. The math is proved theory. But every hardware demo so far (such as 15 = 3 × 5) has been a pre-simplified special case. Published engineering estimates put RSA-2048 at millions of physical qubits running for hours. That is far beyond any machine that exists today.
Why does factoring matter?
Multiply 3 by 5 and you get 15 right away. Now go the other way. Given 15, find the two numbers that multiply to make it. That is factoring. For small numbers it is easy. Now take a 617-digit number, the size used in RSA-2048 encryption. No known method on a normal computer finishes in any useful time. The best one is called the general number field sieve. Its run time still grows faster than any fixed power of 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. Think of a padlock that anyone can snap shut, but only someone who knows the two secret factors can open.
In 1994 Peter Shor proved something big. A large enough quantum computer could factor an n-digit number in a time that grows only like a fixed power of n. That is a true exponential gain over the best known normal method. It is proved theory. The algorithm is correct, full stop. What is not settled is the engineering. Nobody has a machine anywhere close to running it at code-breaking size.
This chapter walks through how the algorithm works. It runs the algorithm's quantum heart on a small circuit whose output you can predict exactly. Then it 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.)
- How does factoring become period finding?
- Where does the quantum computer come in?
- What should the QFT show for a period-2 pattern?
- Run the heart of Shor: reading a period with the QFTINTERACTIVE
- Shift the comb — the offset doesn't matterINTERACTIVE
- Why can't we run the real thing at scale?
- How far away is RSA-2048, really?
- What does this look like on real hardware today?
You’ve read the opening of chapter 9. Pro unlocks the other 8 sections — plus every chapter of every course, with circuits you can run right on the page. That’s $11.99 a month, about the price of a coffee, or $99.99 a year (save 30%). The first chapter of every course, and the whole math course, stay free.