Mathematics of Computation

Evaluation of discrete logarithms in a group of $p$

-torsion points of an elliptic curve in characteristic $p$

Author(s): I. A. Semaev.
Journal: Math. Comp. 67 (1998), 353-356.
MSC (1991): Primary 94A60
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

1.: V. Miller, Use of elliptic curves in cryptography, Advances in Cryptology-Crypto '85, Springer-Verlag, New York, 1986, 417-426. MR 88b:68040
2.: N. Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203-209. MR 88b:94017
3.: 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.
4.: , International Conference ``Modern Problems in Number Theory'', Russia, Tula, Sept. 20-25, 1993, Abstracts of papers.
5.: G. Frey and H.-G. Ruck, A remark concerning $m$ -divisibility and the discrete logarithm in the divisor class group of curves, Math. Comp. 62 (1994), 865-874. MR 94h:11056
6.: S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over and its cryptographic significance, IEEE Trans. Inform. Theory, IT-24 (1978), 106-110. MR 58:4617
7.: J. M. Pollard, Monte-Carlo methods for index computation $(\operatorname{mod}p)$ , Math. Comp. 32 (1978), 918-924. MR 58:10684
8.: J. H. Silverman, The arithmetic of elliptic curves, Springer-Verlag, 1986. MR 87g:11070
9.: J. P. Serre, Sur la topologie des variétés algébriques en caractéristique $p$ , Sympos. Internac. Topologia Algebraica, Mexico City, 1956, 24-53. MR 20:4559
10.: 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''.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS