CoChat

The DOI matches its Crossref record; 39 of the 39 references it cites were found in a registry or an index.

Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms

Open access
Roetteler, Martin, Naehrig, Michael, Svore, Krysta M., Lauter, Kristin · 2017 · Lecture Notes in Computer Science

Abstract

We give precise quantum resource estimates for Shor's algorithm to compute discrete logarithms on elliptic curves over prime fields. The estimates are derived from a simulation of a Toffoli gate network for controlled elliptic curve point addition, implemented within the framework of the quantum computing software tool suite LIQ$Ui|\rangle$. We determine circuit implementations for reversible modular arithmetic, including modular addition, multiplication and inversion, as well as reversible elliptic curve point addition. We conclude that elliptic curve discrete logarithms on an elliptic curve defined over an $n$-bit prime field can be computed on a quantum computer with at most $9n + 2\lceil\log_2(n)\rceil+10$ qubits using a quantum circuit of at most $448 n^3 \log_2(n) + 4090 n^3$ Toffoli gates. We are able to classically simulate the Toffoli networks corresponding to the controlled elliptic curve point addition as the core piece of Shor's algorithm for the NIST standard curves P-192, P-224, P-256, P-384 and P-521. Our approach allows gate-level comparisons to recent resource estimates for Shor's factoring algorithm. The results also support estimates given earlier by Proos and Zalka and indicate that, for current parameters at comparable classical security levels, the number of qubits required to tackle elliptic curves is less than for attacking RSA, suggesting that indeed ECC is an easier target than RSA.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1007/978-3-319-70697-9_9

Cites

39 of 39 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

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?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 37 references

Research works printed but not linked: 8

  1. Beauregard, S.: Circuit for Shor’s algorithm using 2n+3 qubits. Quantum Inf. Comput. 3(2), 175–185 (2003)
  2. Haner, T., Roetteler, M., Svore, K.M.: Factoring using $$2n\,{+}\,2$$ qubits with Toffoli based modular multiplication. Quantum Inf. Comput. 18(7&8), 673–684 (2017)
  3. Maslov, D., Mathew, J., Cheung, D., Pradhan, D.K.: An O(m$${^{2}}$$)-depth quantum algorithm for the elliptic curve discrete logarithm problem over GF(2$${^{m}})$$ $${^{a}}$$. Quantum Inf. Comput. 9(7), 610–621 (2009)
  4. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
  5. Pollard, J.M.: Monte Carlo methods for index computation mod p. Math. Comput. 32(143), 918–924 (1978)
  6. Proos, J., Zalka, C.: Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. 3(4), 317–344 (2003)
  7. Selinger, P.: Efficient Clifford$$+T$$ approximation of single-qubit operators. Quantum Inf. Comput. 15(1–2), 159–180 (2015)
  8. Takahashi, Y., Tani, S., Kunihiro, N.: Quantum addition circuits and unbounded fan-out. Quantum Inf. Comput. 10(9&10), 872–890 (2010)

Cited by

See all 265

Metadata

Authors
Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K.
Affiliations
Microsoft (United States) (US)
Corresponding author
Roetteler, Martin
Venue
Lecture Notes in Computer Science
Published
2017
Volume
2017
Pages
241-270
ISSN
  • 0302-9743 (ISSN-L)
  • 1611-3349
OpenAlex
W2949288242
Cited by
212
References
37
Citations by year
2026: 24 · 2025: 24 · 2024: 28 · 2023: 29 · 2022: 33 · 2021: 28 · 2020: 18 · 2019: 12 · 2018: 13 · 2017: 3
FWCI
5.74
Type
conference paper
Language
en
Open access
Licence
Locations
  • Lecture notes in computer science (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • IACR Cryptology ePrint Archive (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
Keywords
elliptic curve discrete logarithm problem, Shor's algorithm, quantum resource estimation, qubit requirements, quantum circuit complexity, elliptic curve cryptography, post-quantum cryptography

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.

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: Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. https://app.cochat.ai/papers/10.1007/978-3-319-70697-9_9
The paper
Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017). Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-319-70697-9_9

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.