Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

The DOI matches its Crossref record; 84 of the 86 references it cites were found in a registry or an index, and 2 are not checked yet; 66 of the 87 sources its claims cite were checked for support.

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

Open access
Gidney, Craig, Ekerå, Martin · 2021 · Quantum

Abstract

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 3n+0.002nlg⁡n logical qubits, 0.3n3+0.0005n3lg⁡n Toffolis, and 500n2+n2lg⁡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.

Verified 2026-10-05 · 2 references not checked yet

Overview

CoChat Summary

TL;DR

Gidney and Ekerå combine several optimizations to Shor’s algorithm and its Ekerå–Håstad derivatives to sharply reduce the cost of factoring RSA integers and computing finite-field discrete logarithms on a fault-tolerant quantum computer. Their headline estimate is factoring a 2048-bit RSA integer in 8 hours using 20 million noisy qubits, with spacetime volume about a hundredfold lower than comparable earlier estimates.

Key findings

  • The construction reduces the abstract-circuit cost for factoring an \(n\)-bit RSA integer to \(3n + 0.002n\lg n\) logical qubits, \(0.3n^3 + 0.0005n^3\lg n\) Toffolis, and \(500n^2 + n^2\lg n\) measurement depth.
  • For \(n=2048\), Table 3 reports 20 megaqubits, 5.1 hours per run, 5.9 expected megaqubitdays, and a 31% retry risk; the title/abstract advertise 8 hours using 20 million noisy qubits.
  • The paper estimates the spacetime volume is a hundredfold less than comparable earlier works (Van Meter et al. 2009, Jones et al. 2010, Fowler et al. 2012, Gheorghiu et al. 2019), and the Toffoli count is over 10× lower than previous works.
  • For \(n=2048\), the implementation needs approximately 3 billion CCZ states, with total distillation error 6.4% using level 1 code distance 17 and level 2 code distance 27; at code distance 27 the topological error probability is approximately 27%, implying roughly 1.4 repeats on average.

Methods

  • The construction starts from Shor’s algorithm and Ekerå–Håstad’s short-discrete-logarithm algorithm, then applies windowed arithmetic, Zalka’s coset representation of modular integers, oblivious carry runways, and a reaction-limited spacetime layout for lookup additions.
  • Cost estimates are given in the abstract circuit model and under physical assumptions for superconducting qubits: planar nearest-neighbor connectivity, physical gate error rate \(10^{-3}\), surface-code cycle time 1 microsecond, and reaction time 10 microseconds.
  • Parameters such as code distances, window sizes, runway spacing, and padding offset are optimized by minimizing a skewed expected spacetime volume \(s^{1.2} \cdot t/(1-\epsilon)\) over enumerated combinations; estimates cover RSA moduli from 1024 to 16384 bits and finite-field discrete logarithms.

Limitations

  • The paper states large systemic uncertainties: doubling or halving the physical gate error rate would change the required qubit count by more than 10%, and the estimates are intended as ballpark figures, not exact predictions.
  • The paper notes that the runtime estimate ignores that at larger problem sizes lookups become slower because the minimum code distance increases.
  • The paper states that code distance 27 at \(n=2048\) is “pushing the limits of feasibility” with about 27% topological error and roughly 1.4 expected repeats; increasing to distance 29 would raise qubit count by 15% but reduce error by about a factor of 10. The text also makes evident that no hardware demonstration is performed and that not all optimizations are directly applicable to elliptic-curve arithmetic.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.22331/q-2021-04-15-433

Cites

84 of 86 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

42 Valid · 16 Not valid · 10 Not checked · 76 Own results and interpretations

47 more claims · 15 with their cited sources checked

Create a free account to see all 144 claims and to verify the 1 reference still open.

See all claims — free account
  • It may state two separate claims as one. 52
  • Probably not a substantial claim. 55
  • The quote only partly states this claim. 1

Create a free account to see these claims.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

6 more claims about this paper

Create a free account to see every claim other papers make about this one.

See all claims — free account

Citations

Cites

Show all 69 references

Research works printed but not linked: 4

  1. A. A. Karatsuba and Y. P. Ofman. Multiplication of many-digital numbers by automatic computers. Doklady Akademii Nauk SSSR, 145 (2): 293–294, 1962. URL http://mi.mathnet.ru/eng/dan/v145/i2/p293.
  2. A. K. Lenstra. Key Lengths. In The Handbook of Information Security, chapter 6. 2004. URL https://infoscience.epfl.ch/record/164539/files/NPDF-32.pdf.
  3. C. Pomerance. A Tale of Two Sieves. Notices of the AMS, 43 (12): 1473–1485, 1996. URL https://www.ams.org/notices/199612/pomerance.pdf.
  4. O. Schirokauer. On pro-finite groups and on discrete logarithms. PhD thesis, University of California, Berkeley, May 1992.

Cited by

See all 830

Metadata

Authors
Gidney, C., & Ekerå, M.
Affiliations
  • Google (United States) (US)
  • Swedish Armed Forces (SE)
Venue
Quantum
Published
2021-04-15
Volume
5
Pages
433
ISSN
2521-327X (ISSN-L)
OpenAlex
W2946582523
Cited by
830
References
69
Citations by year
2026: 149 · 2025: 195 · 2024: 151 · 2023: 140 · 2022: 87 · 2021: 63
FWCI
38.76
Type
journal article
Language
en
Open access
Locations
  • Quantum (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
  • Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
Keywords
integer factorization, discrete logarithm problem, quantum algorithms, Shor's algorithm, noisy qubits, superconducting qubits, surface code, Toffoli gate, measurement depth

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

The claim verdicts this report counts are experimental: their accuracy is not yet measured.

A language model drew the claims from the paper on 2026-09-29, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-09-29 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Cited sources are checked with a language model’s help (gpt-6-sol and qwen3.8-omni-flash).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. https://app.cochat.ai/papers/10.22331/q-2021-04-15-433
The paper
Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum. https://doi.org/10.22331/q-2021-04-15-433

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.