RSA-2048 Once Needed 20 Million Qubits. Now the Estimate Is Below 100,000.

Quantum computers are getting closer to the cryptographic systems we depend on. But the most interesting part isn't just the smaller number of qubits. It's what researchers changed to get there.

Imagine sending a confidential message over the internet. You open a banking website, enter your credentials, and see the familiar padlock symbol in your browser.

Behind that ordinary interaction, mathematics is doing something extraordinary. Cryptographic algorithms are protecting information that travels between your device and the server.

One of the technologies that helped make this possible is RSA. For decades, RSA has been an important part of public-key cryptography. Its security relies on a mathematical problem that is extremely difficult for conventional computers to solve at sufficiently large key sizes: factoring a large integer into its prime factors.

But quantum computing introduces a different possibility.

In 1994, mathematician Peter Shor demonstrated that a sufficiently powerful fault-tolerant quantum computer could factor large integers much more efficiently than known classical algorithms.

And that changes the security picture. For years, researchers estimated that breaking RSA-2048 would require around 20 million physical qubits. Then, in May 2025, a new estimate reduced that requirement to fewer than one million. In February 2026, another proposed architecture pushed the estimate below 100,000. Think about that for a moment. The estimated hardware requirement has fallen dramatically, even though no quantum computer can currently perform this attack.

So what exactly changed?

First, why does RSA matter?

Before discussing quantum computers, let's understand what they are threatening.

RSA is a public-key cryptographic system based on the mathematical relationship between prime numbers and multiplication.

Suppose we select two large prime numbers: p = 61, q = 53

Multiplying them gives: N = p × q = 3233

In RSA, this product N is called the modulus.

Multiplying two large primes is straightforward. But given only their product, recovering the original prime factors becomes extremely difficult when the numbers are sufficiently large.

Real RSA keys use much larger numbers. RSA-2048, for example, uses a modulus that is 2048 bits long. The security assumption is that factoring such a large integer is computationally infeasible for conventional computers within a practical amount of time. This is the foundation of RSA's security.

What happens if a different type of computer can solve the factoring problem much more efficiently?

That is where Shor's algorithm enters the picture.

Shor's algorithm: the quantum connection

In 1994, Peter Shor introduced a quantum algorithm for integer factorization.

The surprising part is that the algorithm does not directly search through every possible factor. Instead, it transforms the factoring problem into a period-finding problem. Let's understand the basic intuition.

Suppose we want to factor an integer N. We choose an integer a that is relatively prime to N and examine the sequence:

a¹ mod N

a² mod N

a³ mod N

a⁴ mod N

…

Because modular arithmetic has a repeating structure, this sequence eventually repeats.

The smallest positive integer r satisfying: aʳ ≡ 1 (mod N) is called the order or period of a modulo N. Finding this period can help us discover the factors of N.

When the necessary conditions are satisfied, we can calculate:

Factor candidates = gcd(aʳᐟ² − 1, N) and gcd(aʳᐟ² + 1, N). Here, gcd means greatest common divisor. These calculations can reveal non-trivial factors of N.

The difficult part is finding the period efficiently. Shor's algorithm uses quantum computation, particularly quantum phase estimation and the quantum Fourier transform, to obtain information about that period.

This is why quantum computing creates a serious theoretical threat to RSA. It is not because quantum computers try every possible factor simultaneously. That explanation is misleading. The advantage comes from exploiting quantum interference and the mathematical structure of the period-finding problem.

The 20-million-qubit estimate

For a long time, one of the most widely discussed resource estimates came from Craig Gidney and Martin Ekerå.

Their work, initially published as a preprint in 2019 and later published in 2021, estimated that a fault-tolerant quantum computer could factor a 2048-bit RSA integer in approximately eight hours using around 20 million noisy physical qubits.

That is an enormous machine.

Why so many qubits?

Because running Shor's algorithm at cryptographically relevant sizes requires much more than preparing a few quantum states and applying gates.

A practical system needs:

• Logical qubits to store quantum information.
• Physical qubits to implement error correction.
• Reliable quantum gates.
• Fault-tolerant arithmetic operations.
• Resources for non-Clifford operations.
• Measurement and control systems.
• A sufficiently low logical error rate over a long computation.

The distinction between physical and logical qubits is particularly important.

A physical qubit is the actual hardware component. A logical qubit is an encoded unit of quantum information protected using quantum error correction. One logical qubit may require many physical qubits. The overhead depends on the error-correcting code, physical error rates, connectivity, target logical reliability, and architecture.

So when researchers estimate the physical qubits required to break RSA, they are estimating the complete machine, not merely counting the qubits needed by the mathematical algorithm.

Then came the reduction: 20 million to less than one million

In May 2025, Craig Gidney published a paper titled:

"How to factor 2048 bit RSA integers with less than a million noisy qubits."

The paper estimated that RSA-2048 could theoretically be factored using fewer than one million noisy physical qubits, with a runtime of less than one week.

That represents roughly a 20-fold reduction compared with the earlier 20-million-qubit estimate. But the most interesting part is how the reduction was achieved.

It was not the result of suddenly inventing a completely new quantum computer. It came from improving the computational architecture. Three ideas were particularly important.

1. Approximate residue arithmetic

Traditional approaches to quantum factoring involve modular arithmetic operations that can require substantial intermediate quantum storage. A 2024 approach by Chevignard, Fouque, and Schrottenloher demonstrated a way to use approximate residue arithmetic with smaller intermediate values. The important insight was that certain intermediate calculations did not need to preserve the same large exact representations used by earlier approaches. This reduced the number of logical qubits needed.

However, the original approach involved a much higher gate count. Gidney's work streamlined the method and substantially reduced that overhead.

This illustrates an important engineering trade-off: Sometimes, reducing memory requirements increases the amount of computation. The challenge is finding a balance between the number of qubits and the number of operations.

2. Yoked surface codes

Quantum error correction is expensive because physical qubits are noisy. The surface code is one of the leading approaches for protecting quantum information. In a simplified picture, it encodes logical information across a larger collection of physical qubits and uses repeated measurements to detect errors.

But storing information while it is not actively being used also consumes resources. Yoked surface codes provide a way to improve the storage efficiency of idle logical qubits by combining layers of error correction.

The result is a reduction in the physical resources required for storing logical information. This is important because a large quantum algorithm needs to store information reliably throughout its execution, not just perform gates.

3. Magic state cultivation

A fault-tolerant quantum computer needs more than ordinary quantum gates. Certain non-Clifford operations are essential for universal quantum computation. A common way to implement them is through magic states.

Preparing sufficiently reliable magic states can require large additional hardware resources. Magic state distillation is one established approach, but it can consume considerable space and processing capacity. Magic state cultivation offers an alternative method for producing high-quality magic states with a different resource trade-off.

By using this technique, the newer RSA estimate reduced the space allocated to certain parts of the computation. Together, these improvements helped reduce the estimated physical qubit requirement.

But there was a trade-off. The newer estimate allowed a longer runtime: less than a week rather than the earlier eight-hour estimate. A smaller quantum computer does not necessarily mean a faster quantum computer.

The story did not stop at one million

Here is where the research becomes even more interesting. In February 2026, researchers introduced an architecture called Pinnacle, based on quantum low-density parity-check codes, commonly known as quantum LDPC or QLDPC codes.

Their paper titled: "The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes"

proposed that RSA-2048 factoring could be performed using fewer than 100,000 physical qubits under specified hardware assumptions. That is another substantial reduction.

Why does this matter?

Because the surface code, despite its advantages, can have considerable physical-qubit overhead. It generally requires many physical qubits to protect one logical qubit at a sufficiently low error rate.

QLDPC codes offer a different approach to quantum error correction. They use sparse parity-check structures and can potentially encode more logical information with fewer physical qubits.

The Pinnacle proposal combines these codes with an architecture designed for fault-tolerant computation.

Its components include:

• Processing units built from QLDPC code blocks.
• Measurement systems for logical operations.
• Memory components.
• Magic-state preparation and processing.
• Modular connections between processing units.

The paper's illustrative RSA-2048 configuration estimates fewer than 100,000 physical qubits with a physical error rate of 10⁻³, a code cycle time of one microsecond, and a reaction time of ten microseconds.

Its example configuration estimates a runtime of approximately one month. Notice the trade-off again. The machine becomes much smaller, but the computation takes longer than the original eight-hour estimate. The paper also explores configurations with more physical qubits to achieve shorter runtimes.

This is an important lesson in quantum engineering: hardware requirements cannot be separated from the time required to complete the computation.

Comparing the estimates

Let's put the major milestones side by side.

Research milestoneEstimated physical qubitsEstimated runtimeGidney–Ekerå (2019 estimate)~20 million~8 hoursGidney (2025)Under 1 millionUnder 1 weekPinnacle architecture (2026)Under 100,000About 1 month in the example configuration

These figures are not a simple leaderboard.

They involve different circuit designs, error-correction strategies, and space-time trade-offs. Even when physical error assumptions are similar, the architectures and resource accounting differ.

The 2025 estimate uses a surface-code-based approach. The 2026 Pinnacle proposal uses QLDPC codes. And neither result means that a machine capable of factoring RSA-2048 has been built. They are theoretical resource estimates that help researchers understand what future fault-tolerant systems might require.

Does this mean RSA is already broken?

No…Not even close….

The estimates describe machines that do not currently exist. A useful quantum computer must maintain reliable logical operations throughout a very large computation. It must perform billions of operations while keeping the accumulated logical error sufficiently low.

That is a major engineering challenge. Today's quantum processors have made progress in controlling physical qubits, improving gate fidelity, and demonstrating quantum error correction.

But building a large, fault-tolerant machine capable of executing a cryptographically relevant implementation of Shor's algorithm remains a different level of difficulty.

There is a huge difference between demonstrating a quantum algorithm on a small example and executing it at the scale required to factor RSA-2048. The smaller estimates make the engineering target more concrete. They do not prove that the target has been reached.

Why cybersecurity cannot afford to wait

If a large-scale fault-tolerant quantum computer becomes available, widely deployed public-key cryptographic systems based on integer factorization and discrete logarithms could be vulnerable.

RSA is one example. Elliptic-curve cryptography is also vulnerable to sufficiently powerful quantum attacks using Shor's algorithm. This creates a problem that exists even before a cryptographically relevant quantum computer is built.

Consider a scenario in which an attacker collects encrypted information today and stores it. If the information remains valuable for many years, the attacker may attempt to decrypt it in the future when suitable quantum hardware becomes available. This is often called a harvest-now, decrypt-later strategy. That is why post-quantum cryptography is already receiving serious attention.

In August 2024, NIST published its first three post-quantum cryptography standards:

• FIPS 203: ML-KEM, a key-encapsulation mechanism.
• FIPS 204: ML-DSA, a digital signature algorithm.
• FIPS 205: SLH-DSA, a stateless hash-based digital signature algorithm.

These standards are designed to resist attacks from future quantum computers. The transition is not simply about replacing one encryption algorithm with another. Organizations must identify where vulnerable cryptography is used, update protocols, test implementations, and manage long-lived data and keys. The work needs to begin before the threat becomes an immediate practical attack.

The deeper lesson: quantum progress is not just about qubit count

There is something fascinating about this entire story. The hardware requirements for a quantum attack on RSA have decreased substantially without requiring a breakthrough in the basic idea of Shor's algorithm.

The improvements came from better arithmetic, more efficient quantum circuits, and lower-overhead error-correction architectures. This is a reminder that quantum computing progress is not measured only by how many qubits a company announces.

A smaller logical circuit, a better decoder, a more efficient error-correction code, or an improved magic-state factory can change the requirements of an entire computation. In fact, these improvements are relevant far beyond cryptography.

The same techniques can potentially reduce the resources required for quantum chemistry, materials simulation, and other fault-tolerant quantum algorithms. The bigger question is no longer simply how many qubits we can build. It is how efficiently we can turn imperfect physical qubits into reliable logical computation.

The question we should be asking now

The journey from 20 million physical qubits to fewer than one million was already a major change in how researchers think about the quantum threat to RSA.

The proposal to move below 100,000 makes the story even more interesting. But the numbers should not distract us from the real challenge.

Can we build a machine with the required error rates, connectivity, control systems, and fault-tolerant operations? Can we keep it running reliably for weeks? Can the architecture be implemented at scale rather than existing only as a resource estimate?

Those are the questions that matter. RSA has not been broken by a quantum computer. But the engineering distance to a future cryptographically relevant quantum computer is being reassessed, and the estimates are changing faster than many people expected.

Perhaps the most important quantum computing breakthrough is not building a machine with more qubits. It is discovering how to do more with fewer of them.

The future of cryptography may depend not on how many qubits we can build, but on how reliably we can make them work together.

👏 Enjoyed this read? Clap, share, and follow Sarah Rachel for more insights into quantum computing, AI, and emerging technologies.

References and further reading

1. Gidney, C. and Ekerå, M. (2021). "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits." Quantum. https://arxiv.org/abs/1905.09749
2. Gidney, C. (2025). "How to factor 2048 bit RSA integers with less than a million noisy qubits." https://arxiv.org/abs/2505.15917
3. Webster, P. et al. (2026). "The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes." https://arxiv.org/abs/2602.11457
4. Shor, P. W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring." Proceedings of the 35th Annual Symposium on Foundations of Computer Science.
5. NIST (2024). "Post-Quantum Cryptography Standards: FIPS 203, FIPS 204, and FIPS 205." https://csrc.nist.gov/pubs/fips/203/final