Skip to content
The methodOpen data
Back to the collection

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

Craig Gidney

2025 · arXiv

PhysicsSecurity & cryptography
Read the paper
HN score
1
Mentions
10
Readers
6
Months
6
What’s in a score?

From the 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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

10 selected excerpts · 10 total mentions

Strilanc
Recommendation · rule
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 ten years, on the theory side, the expected cost of cryptographically relevant quantum factoring has dropped by 1000x [1][2]. On the hardware side, fault tolerance demonstrations have gone from repetition code error rates of 1% error per round [3] to 0.00000001% error per round [fig3a of 4], with full quantum codes being demonstrated with an error rate of 0.2% [fig1d of 4] via a 2x reduction in…
Read the full comment
error each time distance is increased by 2. If you want to track progress in quantum computing, follow the gradual spinup of fault tolerance. Noise is the main thing blocking factoring of larger and larger numbers. Once the quality problem is turned into a quantity problem, then those benchmarks can start moving. [0]: https://www.youtube.com/watch?v=nJxENYdsB6c [1]: https://arxiv.org/abs/1208.0928 [2]: https://arxiv.org/abs/2505.15917 [3]: https://arxiv.org/abs/1411.7403 [4]: https://arxiv.org/abs/2408.13687
Original comment OpenSSH Post-Quantum Cryptography
plopilop
Neutral mention · rule
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 estimated we needed ~20 million noisy qubits to factor RSA 2048. In 2025, we know we need fewer than 1 million. [0]. Some other papers even claim the need of 1000 physical qubits but they rely on a very exotic architecture so I would not consider them feasible. Progress on the hardware is also continuing, see [1]. Researchers managed to have functional-ish error correction for the first time last…
Read the full comment
year, and experts in the topic are confident that a cryptographically relevant computer will appear in around 15 years. I personally am less optimistic than the experts (admittedly I am not an expert either), but there is enough activity to get worried for critical infrastructure. Regarding the factoring issue, as you point out factoring 15 and factoring 21 are two very different tasks. The first one can be used to show that your quantum computer is indeed doing quantum computation; the second will prove that you have a functional error correcting code. If you can factor 21, it is probably only a matter of months/maybe a few years until you factor RSA 2048. As Scott Aaronson said [3], "Once you understand quantum fault-tolerance, asking “so when are you going to factor 35 with Shor’s algorithm?” becomes sort of like asking the Manhattan Project physicists in 1943, “so when are you going to produce at least a small nuclear explosion?”" [0] https://arxiv.org/abs/2505.15917 [1] https://sam-jaques.appspot.com/quantum_landscape [2] https://globalriskinstitute.org/publication/quantum-threat-t... [3] https://scottaaronson.blog/?p=9665#comment-2029013
Original comment France's Anssi Will Block PQC-Free Products from Certification Starting 2027
qnleigh
Neutral mention · rule
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 disappointing, as factoring 15 only requires 7 logical qubits and ~20 entangling gates, but - Usable logical qubits were a pipe dream only a few years ago. - He's partly coming from the perspective that Nature might somehow make quantum computing impossible by destroying quantum information before it gets 'big enough' to do real quantum computing. Even showing fault tolerance on small scales would be enough…
Read the full comment
to falsify this. One other thing, your numbers are too pessimistic. Multiple technologies have demonstrated 100+ qubits at 3 nines. Factoring cryptographically relevant numbers needs ~1,000,000 qubits at ~3 nines [1]. So like he says, many of the core technological and scientific challenges have been solved, and progress is now largely (though not entirely) a matter of scaling. [1] https://arxiv.org/abs/2505.15917
Original comment Quantum computing: too much to handle
gjrq
Neutral mention · rule
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 assuming a 1MHz "clock" (code cycle time, for the experts). In some ways this is the harder metric to meet than the qubit numbers. Note that the magic of quantum error correction (exponential improvement in the error rate goes both ways): if you could get another 9 in qubit fidelity, you get a much larger improvement in qubit numbers. On the other hand, if you need to split your computation over several systems, things get much worse.
Original comment Why haven't quantum computers factored 21 yet?
qnleigh
Neutral mention · rule
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 plenty of warning before quantum computing causes any major disruptions to daily life. What I would start worrying about is the security of things like messages sent via end-to-end encrypted services like WhatsApp and Signal. Intercepted messages can be saved now and decrypted any time in the future, so it's better to switch to more robust cryptography sooner rather than later. Signal has taken steps in this direction recently: https://arstechnica.com/security/2025/10/why-signals-post-qu.... [0] https://arxiv.org/pdf/2505.15917
Original comment Willow quantum chip demonstrates verifiable quantum advantage on hardware
Strilanc
Neutral mention · rule
> 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 is quantum error correction. [1] estimates distance 25 surface codes would be sufficient for those 7 billion gates (given the physical assumptions it lists). This amplifies the qubit count from 1400 logical qubits to a million physical noisy qubits. Samuel Jacques had a pretty good talk at PQCrypto this year, and he speculates about timelines in it [2]. (I'm the author of this blog post and of [1].) [1]: https://arxiv.org/pdf/2505.15917 [2]: https://www.youtube.com/watch?v=nJxENYdsB6c
Original comment Why haven't quantum computers factored 21 yet?

Keep following the thread.

More in Physics

More from the same topics.