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] Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, 10.1007/BF02252872
  • [3] Stephen Lichtenbaum, Duality theorems for curves over 𝑝-adic fields, Invent. Math. 7 (1969), 120–136. MR 0242831
  • [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] David Mumford, Abelian varieties, Tata Institute of Fundamental Research Studies in Mathematics, No. 5, Published for the Tata Institute of Fundamental Research, Bombay; Oxford University Press, London, 1970. MR 0282985
  • [7] A. M. Odlyzko, Discrete logarithms in finite fields and their cryptographic significance, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 224–314. MR 825593, 10.1007/3-540-39757-4_20
  • [8] J. Tate, 𝑊𝐶-groups over 𝔭-adic fields, Séminaire Bourbaki; 10e année: 1957/1958. Textes des conférences; Exposés 152 à 168; 2e éd. corrigée, Exposé 156, vol. 13, Secrétariat mathématique, Paris, 1958. MR 0105420
  • [9] William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 0265369

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