Evaluation of discrete logarithms in a group of 𝑝-torsion points of an elliptic curve in characteristic 𝑝

Semaev, I.

doi:10.1090/S0025-5718-98-00887-4

Evaluation of discrete logarithms in a group of $p$-torsion points of an elliptic curve in characteristic $p$
HTML articles powered by AMS MathViewer

by I. A. Semaev PDF

Math. Comp. 67 (1998), 353-356 Request permission

Abstract:

We show that to solve the discrete log problem in a subgroup of order $p$ of an elliptic curve over the finite field of characteristic $p$ one needs $O(\ln p)$ operations in this field.

References

Victor S. Miller, Use of elliptic curves in cryptography, Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985) Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417–426. MR 851432, DOI 10.1007/3-540-39799-X_{3}1
Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-5
A. Menezes, S. Vanstone, and O. Tatsuaki, Reducing elliptic curve logarithms to logarithms in a finite field, Proc. 23rd ACM Sympos. Theory of Computing, 1991, pp. 80–89.
I. A. Semaev, Bystryĭ algoritm vyqisleniya sparivaniya A. Veĭlya na èlliptiqeskoĭ krivoĭ, International Conference “Modern Problems in Number Theory”, Russia, Tula, Sept. 20–25, 1993, Abstracts of papers.
Gerhard Frey and Hans-Georg Rück, A remark concerning $m$-divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp. 62 (1994), no. 206, 865–874. MR 1218343, DOI 10.1090/S0025-5718-1994-1218343-6
Stephen C. Pohlig and Martin E. Hellman, An improved algorithm for computing logarithms over $\textrm {GF}(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory IT-24 (1978), no. 1, 106–110. MR 484737, DOI 10.1109/tit.1978.1055817
J. M. Pollard, Monte Carlo methods for index computation $(\textrm {mod}\ p)$, Math. Comp. 32 (1978), no. 143, 918–924. MR 491431, DOI 10.1090/S0025-5718-1978-0491431-9
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1986. MR 817210, DOI 10.1007/978-1-4757-1920-8
Jean-Pierre Serre, Sur la topologie des variétés algébriques en caractéristique $p$, Symposium internacional de topología algebraica International symposium on algebraic topology, Universidad Nacional Autónoma de México and UNESCO, Mexico City, 1958, pp. 24–53 (French). MR 0098097
H.-G. Ruck, A remark on the paper “Evaluation of discrete logarithms on some elliptic curves, by I. A. Semaev”, communication to “Mathematics of Computation”.