Wondering whether quantum computers can really break your encryption? Shor’s algorithm is a quantum method that factors large integers efficiently, which is why RSA is considered vulnerable once large, error-corrected machines exist.
This guide is part of our wider coverage of quantum computing.
| Item | Value |
|---|---|
| Year Shor published his factoring paper | 1994 |
| Benchmark target | 2048-bit RSA integer (a 617-digit number) |
| 2019 estimate (Gidney and Ekerå) | 20 million noisy qubits, eight hours |
| 2025 estimate (Gidney) | Fewer than one million noisy qubits, less than a week |
| Assumed gate error rate | 0.1% |
| Assumed surface code cycle time | 1 microsecond |
These figures come from Gidney’s 2025 paper and a May 2025 report in The Quantum Insider. Estimates can change, so check the source before you rely on them.
What Shor’s algorithm actually does
Shor’s algorithm traces back to a 1994 paper by Peter Shor showing that quantum computers could efficiently factor integers, which meant the RSA cryptosystem was not secure against them, as Gidney’s 2025 paper recounts.
The Quantum Insider describes the result as a discovery that quantum computers could factor large numbers exponentially faster than classical computers. That speed-up is the reason a problem that is hard for ordinary machines becomes a cryptographic worry.
If qubits are new to you, start with our explainer on what is a qubit. The practical difficulty is not the idea but the engineering: the algorithm needs a very large, reliable machine to do arithmetic on huge numbers.
Why a 2048-bit number is the benchmark
Researchers usually measure progress against RSA-2048, a 2048-bit key that represents a 617-digit number made by multiplying two large primes, according to The Quantum Insider.
The same report says the security of this standard underpins much of today’s online banking, email and digital certificates. It relies on how hard conventional methods find it to factor such large numbers.
How the qubit estimate shrank from 2019 to 2025
In 2019, Gidney and Ekerå estimated that a 2048-bit RSA integer could be factored in eight hours by a quantum computer with 20 million noisy qubits. Gidney’s 2025 paper estimates less than a week with fewer than a million noisy qubits.
The Quantum Insider says the result rests on three key innovations. According to Gidney’s paper, the qubit saving comes mainly from these changes:
- approximate residue arithmetic, which keeps intermediate values small;
- yoked surface codes, which store idle logical qubits more compactly;
- magic state cultivation, which needs less space than magic state distillation.
There is a trade-off. An earlier method by Chevignard, Fouque and Schrottenloher used only a bit more than half as many logical qubits as the 2019 design but about 2 trillion Toffoli gates, against 3 billion in 2019, which Gidney calls roughly 1000x more Toffolis for a 6x reduction in space. Gidney’s 2025 paper cuts the Toffoli count by over 100x compared with that method, and the longer runtime comes mainly from performing more Toffoli gates and using fewer magic state factories than in 2019.

What does the 2025 estimate assume?
The estimate is only as realistic as its hardware model. The Quantum Insider’s summary and the paper point to these requirements:
- a square grid of qubits with nearest neighbor connections;
- a gate error rate of no higher than 0.1%;
- a surface code cycle time of 1 microsecond;
- a control system able to react within 10 microseconds;
- about five days of continuous operation across more than 6.5 billion Toffoli gate operations.
Surface codes are a form of quantum error correction, and the whole design depends on them working at scale. As of the May 2025 report, no existing quantum computer can meet the performance requirements.
Approximate methods also add a small failure probability to each run. The same report says repeated trials and statistical filtering compensate for it, but it cannot be eliminated entirely.
Newer proposals trade qubits for time
A February 2026 analysis called Pinnacle suggests that quantum LDPC codes could bring the footprint to approximately 100,000 physical qubits, according to the Quantum Computing Report. The same report, dated March 6, 2026, says the runtime rises to approximately one month.
That report also notes the analysis had not yet undergone formal peer review and needs non-local qubit connectivity. It adds that the design needs classical decoding within a 10-microsecond window, a requirement not yet demonstrated at this scale.
The pattern across these papers is a trade among qubits, runtime and hardware demands. No single number settles how close a real attack is.
What this means for you
Gidney points out that this isn’t a call to panic, and the same report says the threat remains hypothetical. It also notes the study could prompt experts to reassess the urgency of post-quantum cryptography deployment.
The report adds that major hardware firms such as IBM, Quantinuum and PsiQuantum have published multi-year roadmaps targeting systems with hundreds of thousands to millions of qubits by the early 2030s. Those are company plans, not guarantees.
The useful takeaway is that the published estimate for factoring a 2048-bit RSA integer fell from 20 million noisy qubits in 2019 to fewer than one million noisy qubits in 2025, so treat any single figure as a snapshot.
Frequently asked questions
What is Shor’s algorithm in simple terms?
Show answer
It is the quantum method from Peter Shor’s 1994 paper showing that quantum computers could efficiently factor integers, which meant RSA was not secure against them.
Can Shor’s algorithm break RSA today?
Show answer
Not by the estimates’ own account. In its May 2025 coverage, The Quantum Insider says the hardware to execute such a factoring attack is not yet available, and that Gidney’s analysis treats the threat as hypothetical.
Why do the qubit estimates differ between papers?
Show answer
Each paper makes different assumptions and trade-offs. Gidney’s 2025 estimate uses a square grid with nearest neighbor connections, while the Pinnacle analysis needs non-local qubit connectivity.
Why is RSA-2048 the usual target?
Show answer
It is a 2048-bit key representing a 617-digit number, and much of today’s online banking, email and digital certificates relies on this kind of standard.



