Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A remark concerning $ m$-divisibility and the discrete logarithm in the divisor class group of curves

Authors: Gerhard Frey and Hans-Georg Rück
Journal: Math. Comp. 62 (1994), 865-874
MSC: Primary 11G20; Secondary 14G15, 94A60
MathSciNet review: 1218343
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The aim of this paper is to show that the computation of the discrete logarithm in the m-torsion part of the divisor class group of a curve X over a finite field $ {k_0}$ (with $ {\operatorname{char}}({k_0})$ prime to m), or over a local field k with residue field $ {k_0}$, can be reduced to the computation of the discrete logarithm in $ {k_0}{({\zeta _m})^ \ast }$. For this purpose we use a variant of the (tame) Tate pairing for Abelian varieties over local fields. In the same way the problem to determine all linear combinations of a finite set of elements in the divisor class group of a curve over k or $ {k_0}$ which are divisible by m is reduced to the computation of the discrete logarithm in $ {k_0}{({\zeta _m})^ \ast }$.

References [Enhancements On Off] (What's this?)

  • [1] B. Kaliski, Elliptic curves and cryptology: A pseudorandom bit generator and other tools, Ph.D. thesis, M.I.T., 1988.
  • [2] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), 139-150. MR 1007215 (90k:11165)
  • [3] S. Lichtenbaum, Duality theorems for curves over p-adic fields, Invent. Math. 7 (1969), 120-136. MR 0242831 (39:4158)
  • [4] V. Miller, Short programs for functions on curves, unpublished manuscript, 1986.
  • [5] A. Menezes, S. Vanstone, and T. Okamato, Reducing elliptic curve logarithms to logarithms in a finite field, preprint.
  • [6] D. Mumford, Abelian varieties, Oxford Univ. Press, New York, 1970. MR 0282985 (44:219)
  • [7] A. Odlyzko, Discrete logarithms and their cryptographic significance, Advances in Cryptology: Proceedings of Eurocrypt '84, Lecture Notes in Comput. Sci., vol. 209, Springer-Verlag, Berlin and New York, 1985, 224-314. MR 825593 (87g:11022)
  • [8] J. Tate, WC-groups over p-adic fields, Sem. Bourbaki, no. 156, December 1957, 13p. MR 0105420 (21:4162)
  • [9] W. C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École. Norm. Sup. 2 (1969), 521-560. MR 0265369 (42:279)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11G20, 14G15, 94A60

Retrieve articles in all journals with MSC: 11G20, 14G15, 94A60

Additional Information

Article copyright: © Copyright 1994 American Mathematical Society

American Mathematical Society