Almost every conversation about quantum risk traces back to one discovery: Shor’s algorithm. Understanding the idea, even roughly, makes the rest of the topic much clearer.
Why RSA is hard to break
RSA encryption relies on a simple fact: multiplying two large prime numbers is easy, but working backwards from the result to find the two primes is extremely hard. RSA-2048 uses a number with 617 decimal digits.
The largest RSA challenge number ever factored with ordinary computers is RSA-250, which has 250 digits. It was broken in 2020 using roughly 2,700 years of combined computer-core time. RSA-2048 is vastly harder.
Elliptic-curve cryptography (ECC) uses a different maths problem, but it has the same weakness against quantum computers.
Shor’s idea in plain words
Shor realised that factoring can be turned into a different task: finding the length of a repeating pattern, called the period, in a sequence of numbers. Ordinary computers are bad at finding very long periods. Quantum computers, thanks to interference, are very good at it, using a step called the quantum Fourier transform.
Once the period is known, ordinary maths finishes the job and reveals the prime factors.
Why it hasn’t happened yet
Running Shor’s algorithm against RSA-2048 needs a large, error-corrected quantum computer. Real experiments have only factored tiny numbers: 15 was factored in 2001, and 21 in 2012. They prove the principle, but they are nowhere near a real threat.
Estimates of the machine needed keep falling. In 2019, Craig Gidney and Martin Ekerå estimated 20 million noisy qubits running for about 8 hours. In 2025, Gidney estimated fewer than one million noisy qubits running for under a week. Today’s largest machines have around a thousand qubits, with less control than those estimates assume.
What it breaks, and what it doesn’t
- ◆Broken: RSA, Diffie–Hellman and elliptic-curve methods such as ECDH and ECDSA, which protect most key exchanges and digital signatures today.
- ◆Not broken: symmetric encryption such as AES and hash functions such as SHA-256. Quantum computers offer only a smaller speed-up against these.
- ◆Not broken: the new NIST post-quantum standards (ML-KEM, ML-DSA and SLH-DSA), which rely on problems Shor’s algorithm does not solve.
task_altKey takeaways
- check_circleShor’s algorithm turns factoring into period-finding, which quantum computers do well.
- check_circleOnly tiny numbers like 15 and 21 have been factored on real quantum hardware so far.
- check_circleEstimates for breaking RSA-2048 fell from 20 million qubits (2019) to under one million (2025).
- check_circleAES and the new post-quantum standards are not broken by Shor’s algorithm.
Sources and further reading
- open_in_newPeter Shor: Polynomial-time algorithms for prime factorization (arXiv)
- open_in_newVandersypen et al. (2001): Experimental realisation of Shor’s algorithm
- open_in_newGidney & Ekerå (2019): How to factor 2048 bit RSA integers in 8 hours
- open_in_newGidney (2025): Factoring RSA-2048 with less than a million noisy qubits