A newly published study claims that a fault-tolerant quantum computer with roughly 100 000 physical qubits could factor the large integers that underpin RSA encryption, a task previously estimated to require millions of qubits. Below, we unpack what has changed, why it matters, and how the cybersecurity community should respond.
1. A Brief Refresher on RSA
RSA secures everything from online banking to software updates by exploiting the practical difficulty of factoring the product of two large prime numbers. A public key (used to encrypt data) can be freely shared, while a private key (needed to decrypt) stays secret. On classical computers, factoring 2048-bit keys is believed to take longer than the age of the universe, making RSA effectively unbreakable—until quantum computing enters the arena.
2. Shor’s Algorithm: The Quantum Game-Changer
In 1994, mathematician Peter Shor devised a quantum algorithm that can factor integers exponentially faster than any known classical method. The catch has always been hardware size and quality: implementing Shor’s algorithm at a scale large enough to break modern RSA keys requires a highly error-corrected quantum machine.
3. From Millions to 100 000 Qubits—What’s Different?
The new research optimizes three critical layers:
- Circuit Design: Fewer quantum gates are required by streamlining modular exponentiation, the most expensive part of Shor’s algorithm.
- Error-Correction Codes: Advanced surface-code layouts reduce the overhead traditionally assumed for fault-tolerance.
- Parallelization: Segments of the computation are executed concurrently, compressing time requirements.
Combined, these refinements drop the physical-qubit requirement from the multi-million scale to roughly 100 000, a reduction of nearly an order of magnitude.
4. The Remaining Engineering Hurdles
4.1 Qubit Quality
Qubits must maintain coherence long enough to execute billions of error-corrected gate operations. Today’s best superconducting and trapped-ion qubits still fall several orders of magnitude short.
4.2 Error-Correction Overhead
Physical qubits are noisy; logical qubits, which behave ideally, are built from hundreds to thousands of physical qubits. Even at 100 000 physical qubits, the device may support only dozens of logical qubits—just enough for a single RSA-cracking run.
4.3 Scalability and Interconnects
Building a monolithic cryogenic system that houses 100 000 qubits while preserving low-latency connectivity is an unprecedented manufacturing challenge.
4.4 Control Electronics and Cooling
Each qubit requires precise microwave or laser control. Routing signals to 100 000 qubits without overwhelming thermal budgets or creating electromagnetic interference is still an open research area.
5. When Could Such a Machine Exist?
Expert forecasts vary widely. Optimists point to linear growth in qubit counts and incremental improvements in decoherence times, predicting a decade-scale horizon. Skeptics note that scaling yields new error modes and engineering bottlenecks, pushing timelines into the 2040s or beyond. As history shows, progress in quantum hardware is nonlinear.
6. Countermeasures: Post-Quantum Cryptography (PQC)
Anticipating quantum threats, NIST is finalizing standards for quantum-resistant algorithms based on lattices, codes, and multivariate polynomials. Migration strategies include:
- Hybrid Key Exchanges: Combine classical RSA/ECC with PQC schemes to hedge against both classical and quantum attacks.
- Cryptographic Agility: Design systems that can swap algorithms with minimal code changes or downtime.
- Data Lifespan Analysis: Prioritize upgrading data that must remain confidential for decades (e.g., health records, military secrets).
7. Key Takeaways
• The qubit threshold for factoring RSA-2048 has dropped from millions to ~100 000, intensifying urgency for quantum-safe cryptography.
• Substantial engineering and physics challenges still stand between today’s prototypes and a 100 000-qubit, fault-tolerant device.
• Organizations should begin migrating to PQC now; waiting for a fully capable quantum adversary could leave long-lived data exposed.
