HackerPapers

arXiv:2505.15917quant-ph

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

Craig Gidney

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.

arXiv comments
Journal reference
DOI
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 7 identifiable commenters in 11 comments across 9 threads, from May 2025 to Jul 2026. Found in 1 HN submission from May 2025 to May 2025. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments9 threads

  1. France's Anssi Will Block PQC-Free Products from Certification Starting 2027 1 comment

    • There has been a lot of new stuff over the last few years. For instance, breaking RSA or ECDSA is requiring much fewer logical qubits than previously thought, and thus fewer physical qubits as well. Progress in error codes, quantum processing etc. made it that in 2019, it was…

      plopilopView on HNParent context

  2. Shor's algorithm: the one quantum algo that ends RSA/ECC tomorrow 1 comment

    • "How to factor 2048 bit RSA integers with less than a million noisy qubits" (https://arxiv.org/abs/2505.15917) is the most up to date paper here, and uses ~1400 logical and ~900k physical

      adgjlsfhk1View on HNParent context

  3. Quantum computing: too much to handle 1 comment

    • From the comments section, Scott says > To clarify — if, before the 2028 presidential election, a fully fault-tolerant Shor’s algorithm was used even just to factor 15 into 3×5, I would view the “live possibility” here as having come to pass. Now that might sound a bit…

      qnleighView on HNParent context

  4. Keeping the Internet fast and secure: introducing Merkle Tree Certificates 1 comment

    • https://arxiv.org/pdf/1208.0928 is a pretty good into to surface codes. https://www.nature.com/articles/s41586-024-08449-y is a paper that shows surface codes work on real computers. https://arxiv.org/abs/2505.15917v1 is the most recent costing of factoring various size of N…

      adgjlsfhk1View on HNParent context

  5. Willow quantum chip demonstrates verifiable quantum advantage on hardware 1 comment

    • The quantum algorithm that would break certain kinds of public key cryptography schemes (not even the core part of Bitcoin blockchains, which are not vulnerable to quantum computers) will take days to weeks to break a single key [0]. This is another reason why we will have…

      qnleighView on HNParent context

  6. Why haven't quantum computers factored 21 yet? 3 comments

    • Latest numbers are about 1e6 qubits with 1e-4 error rate: https://arxiv.org/abs/2505.15917. Gates (in the sense the OP means) is harder to quantify in the error corrected context once you compile to the operations that are native to your code. Total compute time of about a week…

      gjrqView on HNParent context

    • > So how many gates are we talking to factor some "cryptographically useful" number? Table 5 of [1] estimates 7 billion Toffoli gates to factor 2048 bit RSA integers. > Is there some pathway that makes quantum computers useful this century? The pathway to doing billions of gates…

      StrilancView on HNParent context

    • This is already done. Qbits is the size of the state space and gates is the measure of operations (like flops but quantum operations). https://arxiv.org/pdf/2505.15917 shows a factoring algorithm using 1 million qbits and ~10^10 gates.

      adgjlsfhk1View on HNParent context

  7. OpenSSH Post-Quantum Cryptography 1 comment

    • That paper is hilarious, and is correct that there's plenty of shit to make fun of... but there's also progress. I recommend watching Sam Jacques' talk from PQCrypto 2025 [0]. It would be silly to delay PQC adoption because of focusing on the irrelevant bad papers. In the past…

      StrilancView on HNParent context

  8. It Might Be 20 Times Easier for Quantum Computers to Break Bitcoin, Google Says 1 comment

    • Paper: https://arxiv.org/pdf/2505.15917 The focus on Bitcoin appears to be synthesis on Decrypt's part - it's not mentioned once in the paper.

      greyface-View on HNParent context

  9. Google Researcher Lowers Quantum Bar to Crack RSA Encryption 1 comment

    • The linked HTML version of the arxiv paper sucks. Read the pdf, esp for the python code: https://arxiv.org/pdf/2505.15917v1

      rurbanView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.