The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Reducing elliptic curve logarithms to logarithms in a finite field
Open accessAbstract
Previously, no general-purpose algorithm was known for the elliptic curve logarithm problem that ran in better than exponential time.In this paper we demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying hit e field.For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem.The implications of our results to public key cryptography are discussed. , the subgroup of 2? generated by P, and the subgroup of nth roots of unity in Fqk, where n denot es the order of P. The isomorphism is given by the Weil pairing.Since the index-calculus methods for computing logarithms in a finite field have running times that are subexponential, the reduction is useful for the purpose of computing elliptic curve logarithms provided that k is small.This is indeed the case for special classes of elliptic curves, including the
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.
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
Koblitz, N. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866109-5 · Cited by 5,634
The Arithmetic of Elliptic Curves
Silverman, J. H. (1986) · Graduate Texts in Mathematics · doi:10.1007/978-1-4757-1920-8 · Cited by 4,044
Approximate formulas for some functions of prime numbers
Rosser, J. B., & Schoenfeld, L. (1962) · Illinois Journal of Mathematics · doi:10.1215/ijm/1255631807 · Cited by 1,546
Elliptic curves over finite fields and the computation of square roots mod 𝑝
Schoof, R. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777280-6 · Cited by 515
Discrete logarithms in finite fields and their cryptographic significance
Odlyzko, A. M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-39757-4_20 · Cited by 367
Fast evaluation of logarithms in fields of characteristic two
Coppersmith, D. (1984) · IEEE Transactions on Information Theory · doi:10.1109/tit.1984.1056941 · Cited by 297
Lenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100295 · Cited by 285
Coppersmith, D., Odlzyko, A. M., & Schroeppel, R. (1986) · Algorithmica · doi:10.1007/bf01840433 · Cited by 271
Nonsingular plane cubic curves over finite fields
Schoof, R. (1987) · Journal of Combinatorial Theory, Series A · doi:10.1016/0097-3165(87)90003-3 · Cited by 268
The Multiple Polynomial Quadratic Sieve
Silverman, R. D. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866119-8 · Cited by 159
Probabilistic algorithms in finite fields
Ben-Or, M. (1981) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1981.37 · Cited by 159
Factorizations of 𝑏ⁿ±1, 𝑏=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers
Brillhart, J. D., Lehmer, D. H., Selfridge, J. L., Tuckerman, B., & Wagstaff, S. S. (1988) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/022 · Cited by 139
On taking roots in finite fields
Adleman, L. M., Manders, K. L., & Miller, G. L. (1977) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1977.18 · Cited by 119
Fast, Rigorous Factorization and Discrete Logarithm Algorithms
Pomerance, C. B. (1987) · Elsevier eBooks · doi:10.1016/b978-0-12-386870-1.50014-9 · Cited by 97
Massively Parallel Computation of Discrete Logarithms
Gordon, D. M., & McCurley, K. S. (2007) · Springer eBooks · doi:10.1007/3-540-48071-4_22 · Cited by 57
A subexponential-time algorithm for computing discrete logarithms overGF(p^2)
ElGamal, T. (1985) · IEEE Transactions on Information Theory · doi:10.1109/tit.1985.1057075 · Cited by 55
Fast Computation of Discrete Logarithms in GF (q)
Hellman, M. E., & Reyneri, J. M. (1983) · Springer eBooks · doi:10.1007/978-1-4757-0602-4_1 · Cited by 37
The implementation of elliptic curve cryptosystems
Menezes, A., & Vanstone, S. A. (2006) · Springer eBooks · doi:10.1007/bfb0030345 · Cited by 36
Self-citationElliptic curves and cryptography : a pseudorandom bit generator and other tools
Kaliski, B. S. (1988) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 32
On the Implementation of Elliptic Curve Cryptosystems
Bender, A. O., & Castagnoli, G. (2007) · Springer eBooks · doi:10.1007/0-387-34805-0_18 · Cited by 18
Cited by
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
Self-citationElliptic Curve Public Key Cryptosystems
Menezes, A. (1993) · Springer eBooks · doi:10.1007/978-1-4615-3198-2 · Cited by 852
Self-citationA secure and efficient conference key distribution system: Extended abstract
Burmester, M., & Desmedt, Y. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0053443 · Cited by 844
A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography
Malan, D. J., Welsh, M., & Smith, M. D. (2005) · 2004 First Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004. IEEE SECON 2004. · doi:10.1109/sahcn.2004.1381904 · Cited by 712
jPBC: Java pairing based cryptography
De Caro, A., & Iovino, V. (2011) · 2011 IEEE Symposium on Computers and Communications (ISCC) · doi:10.1109/iscc.2011.5983948 · Cited by 703
Metadata
- Authors
- Menezes, A., Vanstone, S., & Okamoto, T.
- Venue
- Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91
- Publisher
- ACM Press
- Published
- 1991
- Pages
- 80-89
- OpenAlex
- W2028358228
- Cited by
- 337
- References
- 20
- FWCI
- 12.70
- Type
- conference paper
- Language
- en
- Open access
- bronze
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
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.