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

Preprint · Craig Gidney

- Archive id: arxiv:2505.15917
- Published: 2025-05-21
- arXiv: https://arxiv.org/abs/2505.15917
- Source URL: https://arxiv.org/abs/2505.15917
- PDF: https://arxiv.org/pdf/2505.15917
- Provenance: arxiv

## Abstract

Planning the transition to quantum-safe cryptosystems requires understanding the cost of quantum attacks on vulnerable cryptosystems. In Gidney+Ekerå 2019, I co-published an estimate stating that 2048 bit RSA integers could be factored in eight hours by a quantum computer with 20 million noisy qubits. In this paper, I substantially reduce the number of qubits required. I estimate that a 2048 bit RSA integer could be factored in less than a week by a quantum computer with less than a million noisy qubits. I make the same assumptions as in 2019: a square grid of qubits with nearest neighbor connections, a uniform gate error rate of $0.1\\%$, a surface code cycle time of 1 microsecond, and a control system reaction time of $10$ microseconds. The qubit count reduction comes mainly from using approximate residue arithmetic (Chevignard+Fouque+Schrottenloher 2024), from storing idle logical qubits with yoked surface codes (Gidney+Newman+Brooks+Jones 2023), and from allocating less space to magic state distillation by using magic state cultivation (Gidney+Shutty+Jones 2024). The longer runtime is mainly due to performing more Toffoli gates and using fewer magic state factories compared to Gidney+Ekerå 2019. That said, I reduce the Toffoli count by over 100x compared to Chevignard+Fouque+Schrottenloher 2024.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Error Correction & Fault Tolerance](https://space-kitty.com/topics/quantum-error-correction)

Cited in dossiers:
- [Quantum Error Correction & Fault Tolerance: State of the Field (October 2026)](https://space-kitty.com/dossiers/quantum-error-correction)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.