The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
Shor's discrete logarithm quantum algorithm for elliptic curves
Open accessAbstract
We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2^n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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 cited source says what the claim attributes to it.
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 [77]
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
Algorithms 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
Circuit for Shor's algorithm using 2n+3 qubits
Beauregard, S. (2003) · Quantum Information and Computation · doi:10.26421/qic3.2-8 · Cited by 206
Fast versions of Shor's quantum factoring algorithm
Zalka, C. (1998) · arXiv · doi:10.48550/arxiv.quant-ph/9806084 · Cited by 73
Self-citation
Research works printed but not linked: 17
- J. Pollard, Factoring with cubic integers, in The Development of the Number Field Sieve, Vol. 1554 of Lecture Notes in Math. (1993)
- J. Pollard, BIT 15 (1975), p.331, also Knuth [], Vol. 2, p.385
- IEEE P1363, Standard Specifications for Public-Key Cryptography, Febru- ary 2000
- M. Ettinger and P. Hoyer, On Quantum Algorithms for Noncommutative Hidden Subgroups, quant-ph/9807029 · arXiv
- R. Jozsa, Quantum Algorithms and the Fourier Transform, Proc. R. Soc. Lond. A (1998) 454, pp.323-337, (also quant-ph/9707033) · arXiv
- A.Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem, quant-ph/9511026 · arXiv
- S.C. Pohlig and M.E. Hellman, An improved algorithm for computing log- arithms over GF (p) and its cryptographic significance, IEEE Transactions on Information Theory, 24 (1978), 106-110.
- J. Chahal, Topics in Number Theory, Plenum Press, New York, 1988
- N. Koblitz, A Course in Number Theory and Cryptography, Springer- Verlag, New York, 1994.
- R. Cleve et. al., Quantum Algorithms revisited, Proc. R. Soc. Lond. A (1998) 454, p.339, (also quant-ph/9708016) · arXiv
- R.B. Griffiths and C.-S. Niu Semiclassical Fourier Transform for Quantum Computation, Phys.Rev.Lett. 76 (1996) pp.3228-3231 (also quant-ph/9511007) · arXiv
- V. Vedral, A. Barenco and A. Ekert, Quantum Networks for Elementary Arithmetic Operations, quant-ph/9511018 · arXiv
- H. Cohen, A Course in Computational Algebraic Number Theory, Springer- Verlag, Berlin, 1993.
- D. Knuth, The Art of Computer Programming, Volumes 1-3, Addison- Wesley 1998
- Eric Bach and Jeffery Shallit, Algorithmic Number Theory, MIT Press, 1996.
- H. Heilbronn, On the average length of a class of finite continued fraction, in Number Theory and Analysis (Papers in Honor of Edmund Landau), pp. 87-96, Plenum, New York, 1969.
- T. Draper, Addition on a Quantum Computer, quant-ph/0008033 · arXiv
Cited by
Sorted by citations
Quantum algorithms: an overview
Montanaro, A. (2016) · npj Quantum Information · doi:10.1038/npjqi.2015.23 · Cited by 1,071
Curve25519: New Diffie-Hellman speed records
Bernstein, D. J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11745853_14 · Cited by 859
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2020) · IEEE Access · doi:10.1109/access.2020.2968985 · Cited by 607
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
Metadata
- Authors
- Proos, J., & Zalka, C.
- Affiliations
- University of Waterloo (CA)
- Venue
- Quantum Information and Computation
- Publisher
- Rinton Press
- Published
- 2003-07
- Volume
- 3
- Issue
- 4
- Pages
- 317-344
- ISSN
- 1533-7146 (ISSN-L)
- OpenAlex
- W2135205181
- Cited by
- 421
- References
- 3
- Citations by year
- 2026: 41 · 2025: 46 · 2024: 46 · 2023: 37 · 2022: 32 · 2021: 31 · 2020: 52 · 2019: 24 · 2018: 20 · 2017: 8 · 2016: 18 · 2015: 5 · 2014: 8 · 2013: 5 · 2012: 7
- FWCI
- 2.78
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Quantum Information and Computation (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- arXiv (Cornell University)
- Quantum Information and Computation
- Funders
- Mitacs
- 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
- Shor's algorithm, discrete logarithm problem, elliptic curve groups, quantum computing, elliptic curve cryptography, qubit requirements, integer factorization, Euclidean algorithm, modular inverse
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
