How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

PDFHTML

We significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer by combining techniques from Shor 1994, Griffiths-Niu 1996, Zalka 2006, Fowler 2012, Ekerå-Håstad 2017, Ekerå 2017, Ekerå 2018, Gidney-Fowler 2019, Gidney 2019. We estimate the approximate cost of our construction using plausible physical assumptions for large-scale superconducting qubit platforms: a planar grid of qubits with nearest-neighbor connectivity, a characteristic physical gate error rate of $10^{-3}$, a surface code cycle time of 1 microsecond, and a reaction time of 10 microseconds. We account for factors that are normally ignored such as noise, the need to make repeated attempts, and the spacetime layout of the computation. When factoring 2048 bit RSA integers, our construction's spacetime volume is a hundredfold less than comparable estimates from earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019). In the abstract circuit model (which ignores overheads from distillation, routing, and error correction) our construction uses $3 n + 0.002 n \lg n$ logical qubits, $0.3 n^3 + 0.0005 n^3 \lg n$ Toffolis, and $500 n^2 + n^2 \lg n$ measurement depth to factor $n$-bit RSA integers. We quantify the cryptographic implications of our work, both for RSA and for schemes based on the DLP in finite fields.
Submitted 23 May 2019 to Quantum Physics [quant-ph]
Published 24 May 2019
Updated 13 Apr 2021
Author comments: 31 pages, 9 figures, 5 tables
https://arxiv.org/abs/1905.09749
https://arxiv.org/pdf/1905.09749.pdf
https://arxiv-vanity.com/papers/1905.09749

View this paper on arXiv.wiki:
https://arxiv.wiki/abs/1905.09749

4 comments

Pixir Dust May 24 2019 08:43 UTC

How about using shor's algorithm?

Edited May 24 2019 08:44 UTC by Pixir Dust

Martin Ekerå in reply to Pixir Dust May 24 2019 10:59 UTC (3 points)

All of these results are for Shor's algorithms. More specifically, the results are for various derivatives of Shor's original algorithms. These derivatives are specialized for problems that are relevant in cryptography. They provide various constant factor improvements with respect to the number of group operations that need to be performed quantumly compared to using Shor's original algorithms.

If you wish to factor arbitrary composite integers (that are not pure powers) using Shor's original order-finding algorithm, then the estimates we provide for the general DLP using Shor's algorithm for the general DLP with modifications (see Table V, the lower safe-prime section) give a good hint of the estimated cost.

Ryan Babbush in reply to Pixir Dust May 24 2019 18:30 UTC (3 points)

See the first sentence of the main text..