MODULE 3 · LESSON 1
Free — no login requiredSign in to track progress, save quiz attempts and enrol in the full course.
Sign in to track progress / enrolShor's Algorithm and the Cryptography Problem
In 1994, Peter Shor showed that a quantum computer could factor large numbers efficiently. It remains the most consequential result in the field, and it is the reason governments fund quantum computing.
Why factoring matters
Multiplying two large prime numbers is easy. Taking the product and recovering the original primes is, as far as anyone knows, extremely hard classically. The difficulty grows so steeply that a sufficiently large product is beyond any foreseeable classical computer.
RSA encryption is built directly on that asymmetry. The public key is essentially a large product. The private key depends on knowing its factors. Anyone who can factor the public key can derive the private key and read everything.
A closely related problem, the discrete logarithm, underpins elliptic curve cryptography and Diffie-Hellman key exchange. Between them these cover the overwhelming majority of public key cryptography in use: HTTPS, VPNs, code signing, secure messaging, banking.
What Shor's algorithm does
The elegance is in the reformulation. Shor's algorithm does not search for factors. It converts factoring into a completely different question.
There is a mathematical fact connecting factoring to periods. If you take a number and repeatedly multiply it by itself modulo the number you want to factor, the results eventually repeat in a cycle. The length of that cycle is the period, and from the period you can compute the factors using ordinary arithmetic.
So factoring reduces to finding the period of a repeating function. Classically that is no easier than the original problem, because finding the period requires evaluating enormously many values.
Quantum mechanics has a natural affinity for periodicity. The quantum Fourier transform is an operation that takes a superposition and produces one in which amplitudes for the wrong period cancel and the true period reinforces.
There is the cancellation mechanism, exactly as Module 2 described. Shor's algorithm is credible precisely because it has one, and this is what distinguishes it from vague claims about evaluating all possibilities.
The result is a genuine exponential speedup. A problem believed intractable classically becomes tractable.
What is threatened and what is not
An important distinction, and one that is frequently blurred.
Threatened by Shor's algorithm. RSA, elliptic curve cryptography, Diffie-Hellman. That is, essentially all public key cryptography currently deployed. These are broken outright, not weakened.
Not threatened in the same way. Symmetric encryption such as AES, and hash functions such as SHA-256. Grover's algorithm, covered next, gives a quadratic improvement against these. The standard response is to double key lengths: AES-256 remains comfortable. This is an adjustment, not a crisis.
So the picture is not that all cryptography fails. It is that the public key layer, the part that establishes secure connections and verifies identities, needs replacing, while the bulk encryption layer needs larger keys.
The hardware reality, and why it is still urgent
Shor's algorithm needs a large, error corrected quantum computer. Estimates for breaking RSA-2048 typically run to millions of physical qubits under current error correction schemes, and the best machines today have a few hundred physical qubits with error rates far above what is required. Module 4 explains that gap properly.
So nothing can be broken today, or soon. Yet the migration is being treated as urgent by every serious standards body, and the reason is a specific attack that does not require the computer to exist yet.
Harvest now, decrypt later. An adversary records encrypted traffic today and stores it. When a capable quantum computer eventually exists, they decrypt the archive.
This inverts the usual timeline. For anything that must stay confidential for a long time, diplomatic cables, medical records, intellectual property, personal data with legal retention requirements, the relevant question is not when quantum computers will arrive. It is whether your data will still matter then.
If data encrypted today must remain secret for fifteen years, and capable machines might exist within fifteen years, then that data is already exposed. The interception happens now, and the decryption merely waits.
Module 6 covers what to do about it.
Published estimates for the resources needed to break RSA-2048 have ranged from roughly a billion physical qubits down to under a million, and headlines periodically announce dramatic reductions. Understanding why the number moves helps you read the news.
The figure depends on several assumptions that each move it by orders of magnitude.
Physical error rates. Error correction overhead depends steeply on how good the underlying qubits are. Better physical qubits need less correction, and a modest improvement in error rate can cut the qubit requirement substantially.
The error correcting code. Most estimates assume the surface code, which is well understood and expensive. Alternatives such as qLDPC codes promise roughly an order of magnitude fewer physical qubits per logical qubit. Switching the assumed code changes the answer dramatically.
Time budget. A machine can trade qubits against runtime. Estimates assuming a computation may run for weeks require fewer qubits than those demanding hours.
Algorithmic improvements. Shor's algorithm as published is not the most efficient known implementation, and refinements continue to reduce the required operations.
So when a paper announces that RSA could be broken with far fewer qubits than previously thought, it is usually changing one of these assumptions rather than reporting new hardware. That is real progress and it is not the same as a machine existing.
The practical guidance for a non-specialist: treat specific dates for a cryptographically relevant quantum computer with caution in both directions. Nobody credible claims it exists, and nobody credible claims it is impossible. Because harvest now, decrypt later removes the date from the decision anyway, you can plan the migration without needing to resolve the argument. That is a fortunate property, and it is why standards bodies proceeded without waiting for consensus on timing.
Why is migrating away from RSA treated as urgent when no quantum computer capable of breaking it exists?
Shor's algorithm
Click to flipA 1994 result giving an exponential speedup for factoring and discrete logarithms, breaking essentially all deployed public key cryptography.
Click to flip backShor's algorithm converts factoring into period finding, where the quantum Fourier transform cancels wrong periods and reinforces the true one, giving a genuine exponential speedup. It breaks RSA, elliptic curve cryptography and Diffie-Hellman outright, while symmetric ciphers and hashes need only larger keys. No machine can do this today and estimates of what it would take vary by orders of magnitude depending on assumptions. The urgency comes from harvest now, decrypt later, which means long-lived data encrypted today is already exposed regardless of when the hardware arrives.