A remark concerning $m$divisibility and the discrete logarithm in the divisor class group of curves
HTML articles powered by AMS MathViewer
 by Gerhard Frey and HansGeorg Rück PDF
 Math. Comp. 62 (1994), 865874 Request permission
Abstract:
The aim of this paper is to show that the computation of the discrete logarithm in the mtorsion 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

B. Kaliski, Elliptic curves and cryptology: A pseudorandom bit generator and other tools, Ph.D. thesis, M.I.T., 1988.
 Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, DOI 10.1007/BF02252872
 Stephen Lichtenbaum, Duality theorems for curves over $p$adic fields, Invent. Math. 7 (1969), 120–136. MR 242831, DOI 10.1007/BF01389795 V. Miller, Short programs for functions on curves, unpublished manuscript, 1986. A. Menezes, S. Vanstone, and T. Okamato, Reducing elliptic curve logarithms to logarithms in a finite field, preprint.
 David Mumford, Abelian varieties, Tata Institute of Fundamental Research Studies in Mathematics, vol. 5, Published for the Tata Institute of Fundamental Research, Bombay by Oxford University Press, London, 1970. MR 0282985
 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, DOI 10.1007/3540397574_{2}0
 J. Tate, $WC$groups over ${\mathfrak {p}}$adic fields, Secrétariat mathématique, Paris, 1958. Séminaire Bourbaki; 10e année: 1957/1958; Textes des conférences; Exposés 152 à 168; 2e éd. corrigée, Exposé 156, 13 pp. MR 0105420
 William C. Waterhouse, Abelian varieties over finite fields, Ann. Sci. École Norm. Sup. (4) 2 (1969), 521–560. MR 265369, DOI 10.24033/asens.1183
Additional Information
 © Copyright 1994 American Mathematical Society
 Journal: Math. Comp. 62 (1994), 865874
 MSC: Primary 11G20; Secondary 14G15, 94A60
 DOI: https://doi.org/10.1090/S00255718199412183436
 MathSciNet review: 1218343