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 accessAbstract
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.
Integrity signals
Registry
Cites
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.
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Pioneer work by the University of Waterloo and Microsoft Research estimated that the number of logical qubits necessary to implement quantum algorithms that can break 256 bit-long digital signatures generated with (EC)DSA, typically used in current blockchain networks, are 150077 and 233078, respectively.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [78]
Experimental — accuracy not yet measured
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
New directions in cryptography
Diffie, W., & Hellman, M. (1976) · IEEE Transactions on Information Theory · doi:10.1109/tit.1976.1055638 · Cited by 14,713
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462 · cited 8×
“Our findings imply that attacking elliptic curve cryptography is indeed easier than attacking RSA, even for relatively small key sizes.”
BackgroundInfluentialAlgorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
A public key cryptosystem and a signature scheme based on discrete logarithms
Elgamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057074 · Cited by 8,059 · cited 1×
“Thirty years after their introduction to cryptography [27,24], they are used to instantiate public key mechanisms such as key exchange [10] and digital signatures [15,20] that are widely deployed in various cryptographic systems.”
BackgroundKoblitz, N. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866109-5 · Cited by 5,634 · cited 1×
“Thirty years after their introduction to cryptography [27,24], they are used to instantiate public key mechanisms such as key exchange [10] and digital signatures [15,20] that are widely deployed in various cryptographic systems.”
BackgroundTor: The Second-Generation Onion Router
Dingledine, R., Mathewson, N., & Syverson, P. (2004) · doi:10.21236/ada465464 · Cited by 4,104
Use of Elliptic Curves in Cryptography
Miller, V. S. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39799-x_31 · Cited by 3,946
Surface codes: Towards practical large-scale quantum computation
Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012) · Physical Review A · doi:10.1103/physreva.86.032324 · Cited by 3,059
Modular multiplication without trial division
Montgomery, P. L. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777282-x · Cited by 2,669 · cited 2×
“In [28], Montgomery introduced a representation for an integer modulo p he called a p-residue that is now called the Montgomery representation.”
Background
Research works printed but not linked: 8
- Beauregard, S.: Circuit for Shor’s algorithm using 2n+3 qubits. Quantum Inf. Comput. 3(2), 175–185 (2003)
- 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)
- 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)
- Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)
- Pollard, J.M.: Monte Carlo methods for index computation mod p. Math. Comput. 32(143), 918–924 (1978)
- Proos, J., Zalka, C.: Shor’s discrete logarithm quantum algorithm for elliptic curves. Quantum Inf. Comput. 3(4), 317–344 (2003)
- Selinger, P.: Efficient Clifford$$+T$$ approximation of single-qubit operators. Quantum Inf. Comput. 15(1–2), 159–180 (2015)
- Takahashi, Y., Tani, S., Kunihiro, N.: Quantum addition circuits and unbounded fan-out. Quantum Inf. Comput. 10(9&10), 872–890 (2010)
Cited by
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
Gidney, C., & Ekerå, M. (2021) · Quantum · doi:10.22331/q-2021-04-15-433 · Cited by 830
“In particular, consider the Toffoli count for computing discrete logarithms over elliptic curves reported by [17].”
BackgroundMethodToward the first quantum simulation with quantum speedup
Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551
“) Quantum algorithms for classically hard instances of the elliptic curve discrete logarithm problem have roughly comparable cost (37).”
BackgroundThe Roadmap to 6G Security and Privacy
Porambage, P., Gur, G., Osorio, D. P. M., Liyanage, M., Gurtov, A., & Ylianttila, M. (2021) · IEEE Open Journal of the Communications Society · doi:10.1109/ojcoms.2021.3078081 · Cited by 416
“The discrete logarithmic problem, which is the basis of current asymmetric cryptography, may become solv-able in polynomial time with the development of quantum algorithms (e.g., Shor) [117].”
BackgroundNoise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers
Murali, P., Baker, J. M., Javadi-Abhari, A., Chong, F. T., & Martonosi, M. (2019) · Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3297858.3304075 · Cited by 411
“A QC system with 72 fully-entangled qubits and sufficiently-precise operations (“gates”) would likely be sufficient to show “quantum advantage” over the largest classical supercomputers, but would still be 5-6 orders of magnitude smaller than the resource requirements of Shor’s well-known QC algorithm for factoring la…”
MethodQuantum Algorithms: A Survey of Applications and End-to-end Complexities
Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., et al. (2023) · RWTH Publications (RWTH Aachen) · doi:10.18154/rwth-2026-02888 · Cited by 359
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
- Publisher
- Springer International Publishing
- 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
- green
- arxiv.org
- Licence
- www.springernature.com/gp/researchers/text-and-data-mining (tdm)
- www.springernature.com/gp/researchers/text-and-data-mining (vor)
- 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.