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

2025/05/21 by Craig Gidney, Gidney, Craig · 14 voices · 68 citations
Computer Science · #Coding theory and cryptography #Quantum Computing Algorithms and Architecture #Cryptography and Residue Arithmetic

paper · pdf · doi:10.48550/arxiv.2505.15917

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.

Citations

• A method for obtaining digital signatures and public-key cryptosystems

Cited by

• Biased-noise qubits: a guide to efficient fault-tolerance using the hierarchy of errors
• Demonstrating Record Fidelity for the Quantum Fourier Transform
• PureMagic: A Dynamic Scheduler for Lattice Surgery
• Remote entanglement need not be the bottleneck for modular trapped-ion quantum computing
• Transversal fault tolerant distributed quantum computing operations
• Performance Model for Hybrid Quantum-Classical Workflows
• Nonlinear photonic architecture for fault-tolerant quantum computing
• Constant-Time Surgery on 2D Hypergraph Product Codes with Near-Constant Space Overhead
• The Pinnacle Architecture: Reducing the cost of breaking RSA-2048 to 100 000 physical qubits using quantum LDPC codes
• Magic state cultivation on a superconducting quantum processor
• Mind the gaps: The fraught road to quantum advantage
• Awesome Quantum Computing Experiments: Benchmarking Experimental Progress Towards Fault-Tolerant Quantum Computation
• Metasurfaces for neutral-atom trapping
• Probing the Planck scale with quantum computation
• Can PCE solve the factorisation problem via optimisation?
• Bias-preserving cat-cat CNOT gate via vacuum-conditional beam-splitter
• Practical advantage beyond the quadratic speedup limit with fully-quantum walks
• The EU Quantum Flagship's Key Performance Indicators for Quantum Computing
• Practical Challenges in Executing Shor's Algorithm on Existing Quantum Platforms
• Advantage in distributed quantum computing with slow interconnects
• A scalable and real-time neural decoder for topological quantum codes
• A manufacturable surface code architecture for spin qubits with fast transversal logic
• Quantum Advantage in Resource Estimation
• Recursive Clifford noise reduction
• Compilation Pipeline for Predicting Algorithmic Break-Even in an Early-Fault-Tolerant Surface Code Architecture
• Mode multiplexing for scalable cavity-enhanced operations in neutral-atom arrays
• Resource assessment of classical and quantum hardware for post-quench dynamics
• Explicit construction of low-overhead gadgets for gates on quantum LDPC codes
• Elevator Codes: Concatenation for resource-efficient quantum memory under biased noise
• Entanglement boosting: Low-volume logical Bell pair preparation for distributed fault-tolerant quantum computation
• The Grand Challenge of Quantum Applications
• Reinforcement Learning Control of Quantum Error Correction
• Realization of a Quantum Streaming Algorithm on Long-lived Trapped-ion Qubits
• The Fast for the Curious: How to accelerate fault-tolerant quantum applications
• Enabling Fast and Accurate Neutral Atom Readout through Image Denoising
• Rational quantum mechanics: Testing quantum theory with quantum computers
• Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms
• Hardware-Tailored Resource Estimation for Magic-State Distillation on Silicon Spin Qubits
• PIQC: Scalable Distributed Quantum Computing via Photonic Integration of Designed Molecular Quantum Nodes
• Decoder Switching: Breaking the Speed-Accuracy Tradeoff in Real-Time Quantum Error Correction
• Platform Architecture for Tight Coupling of High-Performance Computing with Quantum Processors
• Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice
• Surface code scaling on heavy-hex superconducting quantum processors
• Measurement-Based Fault-Tolerant Quantum Computation on High-Connectivity Devices: A Resource-Efficient Approach toward Early FTQC
• Quantum Reverse Mapping: Synthesizing an Optimal Spin Qubit Shuttling Bus Architecture for the Surface Code
• Parallel Spooky Pebbling Makes Regev Factoring More Practical
• Characterizing Space-Constrained Implementability of Quantum Instruments via Signaling Conditions
• Fault-tolerant interfaces for modular quantum computing on diverse qubit platforms
• Low-depth fermion routing without ancillas
• Fast surgery for quantum LDPC codes
• Chiral quantum state circulation from photon lattice topology
• Quantum lattice Boltzmann algorithm for heat transfer with phase change
• High-performance multiplexed readout of superconducting qubits with a tunable broadband Purcell filter
• Time-Based State-Management of Hash-Based Signature CAs for VPN-Authentication
• Power and limitations of distributed quantum state purification
• Robustness of quantum algorithms: Worst-case fidelity bounds and implications for design
• Fold-transversal surface code cultivation
• Efficient QKD in Non-Ideal Scenarios with User-Defined Output Length Requirements
• Learning Neural Decoding with Parallelism and Self-Coordination for Quantum Error Correction
• An exploration of the noise sensitivity of the Shor's algorithm
• Colour Codes Reach Surface Code Performance using Vibe Decoding
• Brace for impact: ECDLP challenges for quantum cryptanalysis
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Magic tricycles: Efficient magic state generation with finite block-length quantum LDPC codes
• Benchmarking quantum computers with any quantum algorithm
• Distributed fault-tolerant quantum memories over a 2xL array of qubit modules
• Performance and Storage Analysis of CRYSTALS Kyber as a Post Quantum Replacement for RSA and ECC
• Modeling Charge Noise in Superconducting Qubits Using Memory Multi-Fractional Brownian Motion
• Almost fault-tolerant quantum machine learning with drastic overhead reduction

Discussions

• arxiv.org/abs/2505.15917 [bsky, 23 points, 1 comments]
• It's time we rename Q-Day to Gidney-Day. arxiv.org/abs/2505.15917 [bsky, 18 points, 0 comments]
• Major update on factoring primes with Shor’s algorithm from Craig Gidney at #Google. - reduced physical #qubit count from 20e6 to 1e6 to break a RSA-2048 bit key, using yoked surface codes, magic stat [bsky, 11 points, 0 comments]
• Factoring RSA 2048 bit keys in <1M qubits from Google... Providing there are no errors, this takes the required factoring estimate down to ~2^19 qubits. We were at 2^10 in Dec 2023, so assuming it dou [bsky, 10 points, 2 comments]
• This astonishing result shows that it can be done with far fewer qubits than imagined before. This is the start of a critical journey—you need to be worried 👉🏼 arxiv.org/abs/2505.15917 [bsky, 6 points, 0 comments]
• Major update on factoring primes with Shor’s algorithm from Craig Gidney at #Google. - reduced physical #qubit count from 20e6 to 1e6 to break a RSA-2048 bit key, using yoked surface codes, magic stat [bsky, 5 points, 0 comments]
• How to factor 2048 bit RSA integers with less than a million noisy qubits [hn, 3 points, 0 comments]
• Google researcher Craig Gidney's new findings: breaking RSA encryption now requires 20x fewer quantum resources than previously estimated. This affects everything: Bitcoin, TLS, PKI infrastructure. Th [bsky, 2 points, 0 comments]
• Bad news for bitcoin arxiv.org/pdf/2505.15917 [bsky, 2 points, 0 comments]
• To break 2048-bit RSA with Shor or Regev algorithm you would need so-called fault tolerant quantum computer . Such computer would be able to carry out several billions of quantum operations on hundred [stackexchange, 2 points]
• Kidney's full article, "How to factor 2048 bit RSA integers with less than a million noisy qubits" is here: arxiv.org/pdf/2505.15917 We'll be updating and linking it on quantum doom clock shortly! [bsky, 0 points, 0 comments]
• Craig Gidney's work tackles that question: arxiv.org/abs/2505.159.... Check out the figures in the appendix: the physical qubits are used quite densely! [bsky, 0 points, 0 comments]
• Craig Gidney published a new paper, “How to factor 2048 bit RSA integers with less than a million noisy qubits.” This is a 20-times reduction from the estimate the same author made six years ago. www. [bsky, 0 points, 0 comments]
• arxiv.org/abs/2505.15917 [bsky, 0 points, 0 comments]

Related

• How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
• Factoring integers with sublinear resources on a superconducting quantum processor
• A comment on "Factoring integers with sublinear resources on a superconducting quantum processor"
• Breaking RSA Security With A Low Noise D-Wave 2000Q Quantum Annealer: Computational Times, Limitations And Prospects
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA