How would a quantum computer break RSA, and why hasn't one yet?

A quantum computer would break RSA by turning the hard problem of factoring into a different one it is good at: finding a repeating pattern. In 1994 the American mathematician Peter Shor devised a quantum algorithm for finding the prime factors of an integer. It runs in polynomial time, while the best classical method, the general number field sieve, takes sub-exponential time. That gap is what puts RSA at risk, and the same algorithm also threatens the Diffie-Hellman key exchange, in both its ordinary and elliptic-curve forms.

The algorithm has two parts. A classical part reduces factoring to order-finding: for a chosen number a, find the smallest positive k such that a to the power k, divided by N, leaves remainder 1. For example, the order of 4 modulo 7 is 3. The quantum part finds that order, using wave interference that amplifies the probability of the right answer, and a few extra steps with Euclid's algorithm turn the order into a factor. Shor said he found the discrete logarithm version first, and that later that week he solved factoring too.

So why is RSA still safe? Because the machines are not there yet. As of 2026, laboratory demonstrations obtain correct results in only a fraction of attempts and have only succeeded with small semiprimes, and the small demonstrations so far compile the circuit using prior knowledge of the solution. Beating classical computers may require millions of qubits because of error correction. In 2019 an estimate said 20 million noisy qubits could factor a 2048-bit RSA number in eight hours; in 2025 Craig Gidney estimated less than a million, in less than a week. The danger is real enough that Shor's algorithm has driven the search for post-quantum cryptography.