Real and imaginary quadratic representations of hyperelliptic function fields
Authors:
Sachar Paulus and HansGeorg Rück
Journal:
Math. Comp. 68 (1999), 12331241
MSC (1991):
Primary 11R58, 14Q05; Secondary 11R65, 14H05, 14H40
Published electronically:
February 15, 1999
MathSciNet review:
1627817
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A hyperelliptic function field can be always be represented as a real quadratic extension of the rational function field. If at least one of the rational prime divisors is rational over the field of constants, then it also can be represented as an imaginary quadratic extension of the rational function field. The arithmetic in the divisor class group can be realized in the second case by Cantor's algorithm. We show that in the first case one can compute in the divisor class group of the function field using reduced ideals and distances of ideals in the orders involved. Furthermore, we show how the two representations are connected and compare the computational complexity.
 1.
William
W. Adams and Michael
J. Razar, Multiples of points on elliptic curves and continued
fractions, Proc. London Math. Soc. (3) 41 (1980),
no. 3, 481–498. MR 591651
(82c:14031), http://dx.doi.org/10.1112/plms/s341.3.481
 2.
Emil
Artin, The collected papers of Emil Artin, Edited by Serge
Lang and John T. Tate, Addison–Wesley Publishing Co., Inc., Reading,
Mass.London, 1965. MR 0176888
(31 #1159)
 3.
I. Biehl, J. Buchmann, C. Thiel: Cryptographic protocols based on discrete logarithms in real quadratic orders. Proceedings of CRYPTO '94. New York: Springer 1995.
 4.
David
G. Cantor, Computing in the Jacobian of a
hyperelliptic curve, Math. Comp.
48 (1987), no. 177, 95–101. MR 866101
(88f:11118), http://dx.doi.org/10.1090/S00255718198708661010
 5.
H.
W. Lenstra Jr., On the calculation of regulators and class numbers
of quadratic fields, Number theory days, 1980 (Exeter, 1980) London
Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press,
Cambridge, 1982, pp. 123–150. MR 697260
(86g:11080)
 6.
David
Mumford, Tata lectures on theta. I, Progress in Mathematics,
vol. 28, Birkhäuser Boston, Inc., Boston, MA, 1983. With the
assistance of C. Musili, M. Nori, E. Previato and M. Stillman. MR 688651
(85h:14026)
David
Mumford, Tata lectures on theta. II, Progress in Mathematics,
vol. 43, Birkhäuser Boston, Inc., Boston, MA, 1984. Jacobian
theta functions and differential equations; With the collaboration of C.
Musili, M. Nori, E. Previato, M. Stillman and H. Umemura. MR 742776
(86b:14017)
 7.
R.
Scheidler, A.
Stein, and Hugh
C. Williams, Keyexchange in real quadratic congruence function
fields, Des. Codes Cryptogr. 7 (1996), no. 12,
153–174. Special issue dedicated to Gustavus J. Simmons. MR 1377761
(97d:94009), http://dx.doi.org/10.1007/BF00125081
 8.
Daniel
Shanks, The infrastructure of a real quadratic field and its
applications, Proceedings of the Number Theory Conference (Univ.
Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972,
pp. 217–224. MR 0389842
(52 #10672)
 9.
Andreas
Stein, Equivalences between elliptic curves and real quadratic
congruence function fields, J. Théor. Nombres Bordeaux
9 (1997), no. 1, 75–95 (English, with English
and French summaries). MR 1469663
(98d:11144)
 10.
Henning
Stichtenoth, Algebraic function fields and codes,
Universitext, SpringerVerlag, Berlin, 1993. MR 1251961
(94k:14016)
 1.
 W. W. Adams, M. J. Razar: Multiples of points on elliptic curves and continued fractions. Proc. London Math. Soc. 41 (1980). pp. 481  498. MR 82c:14031
 2.
 E. Artin: Quadratische Körper im Gebiete der höheren Kongruenzen I. Mathematische Zeitschrift 19 (1924). pp. 153  206; reprinted in S. Lang, J. Tate (eds.): The collected papers of Emil Artin. Reading, Mass.: Addison Wesley 1965. MR 31:1159
 3.
 I. Biehl, J. Buchmann, C. Thiel: Cryptographic protocols based on discrete logarithms in real quadratic orders. Proceedings of CRYPTO '94. New York: Springer 1995.
 4.
 D. G. Cantor: Computing in the Jacobian of a hyperelliptic curve. Mathematics of Computation 48 (1987). pp. 95  101. MR 88f:11118
 5.
 H. W. Lenstra, Jr.: On the calculation of regulators and class numbers of quadratic fields. Number Theory Days (Exeter, 1980; J. V. Armitage, ed.), London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, 1982, pp. 123  150. MR 86g:11080
 6.
 D. Mumford: Tata Lectures on Theta I, II. Boston: Birkhäuser Verlag 1983/84. MR 85h:14026; MR 86b:14017
 7.
 R. Scheidler, A. Stein, H. C. Williams: Keyexchange in real quadratic congruence function fields. Designs, Codes and Cryptography 7 (1996). pp. 153  174. MR 97d:94009
 8.
 D. Shanks: The infrastructure of a real quadratic field and its applications. Proc. Number Theory Conf., Univ. of Colorado, Boulder, CO, 1972, pp. 217  224. MR 52:10672
 9.
 A. Stein: Equivalences between elliptic curves and real quadratic congruence function fields. Journal de Théorie des Nombres de Bordeaux 9. 1997. pp. 79  95. MR 98d:11144
 10.
 H. Stichtenoth: Algebraic Function Fields and Codes. Berlin; Heidelberg: Springer 1993. MR 94k:14016
Similar Articles
Retrieve articles in Mathematics of Computation of the American Mathematical Society
with MSC (1991):
11R58,
14Q05,
11R65,
14H05,
14H40
Retrieve articles in all journals
with MSC (1991):
11R58,
14Q05,
11R65,
14H05,
14H40
Additional Information
Sachar Paulus
Affiliation:
Institut für Theoretische Informatik, TU Darmstadt, Alexanderstraße 10, 64283 Darmstadt (Germany)
Email:
sachar@cdc.informatik.thdarmstadt.de
HansGeorg Rück
Affiliation:
Institut für Experimentelle Mathematik, Universität GH Essen, Ellernstr.29, 45326 Essen (Germany)
Email:
rueck@expmath.uniessen.de
DOI:
http://dx.doi.org/10.1090/S0025571899010662
PII:
S 00255718(99)010662
Keywords:
Hyperelliptic curves,
divisor class groups,
real quadratic model
Received by editor(s):
July 24, 1997
Received by editor(s) in revised form:
November 3, 1997, and January 20, 1998
Published electronically:
February 15, 1999
Article copyright:
© Copyright 1999
American Mathematical Society
