Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Explicit bounds and heuristics on class numbers in hyperelliptic function fields

Authors: Andreas Stein and Edlyn Teske
Journal: Math. Comp. 71 (2002), 837-861
MSC (2000): Primary 11Y16, 11Y40, 11R29, 11R58; Secondary 11M38, 11R65
Published electronically: October 4, 2001
MathSciNet review: 1885633
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we provide tight estimates for the divisor class number of hyperelliptic function fields. We extend the existing methods to any hyperelliptic function field and improve the previous bounds by a factor proportional to $g$ with the help of new results. We thus obtain a faster method of computing regulators and class numbers. Furthermore, we provide experimental data and heuristics on the distribution of the class number within the bounds on the class number. These heuristics are based on recent results by Katz and Sarnak. Our numerical results and the heuristics imply that our approximation is in general far better than the bounds suggest.

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

  • [ADH94] L. Adleman, J. DeMarrais, and M.-D. Huang.
    A subexponential algorithm for discrete logarithms over the rational subgroup of the jacobians of large genus hyperelliptic curves over finite fields.
    In Algorithmic Number Theory Seminar ANTS-I, volume 877 of Lecture Notes in Computer Science, pages 28-40. Springer, 1994. MR 96b:11078
  • [Art24] E. Artin.
    Quadratische Körper im Gebiete der höheren Kongruenzen I, II.
    Math. Zeitschr., 19:153-206, 1924.
  • [Bac95] E. Bach.
    Improved approximations for euler products.
    In Proc. CNTA-4 (Canadian Math. Soc. Conference), volume 15, pages 13-28, 1995. MR 96i:11124
  • [Bir68] B. Birch.
    How the number of points of an elliptic curve over a fixed prime field varies.
    J. London Math. Soc., 43:57-60, 1968. MR 37:6242
  • [BT00] S. R. Blackburn and E. Teske.
    Baby-step giant-step algorithms for non-uniform distributions.
    In Algorithmic Number Theory Seminar ANTS-IV, volume 1838 of Lecture Notes in Computer Science, pages 153-168. Springer-Verlag, 2000.
  • [CF96] J. W. S. Cassels and E. V. Flynn.
    Prolegomena to a middlebrow arithmetic of curves of genus $2$, volume 230 of London Mathematical Society Lecture Series.
    Cambridge University Press, 1996. MR 97i:11071
  • [Deu73] M. Deuring.
    Lectures on the Theory of Algebraic Functions of One Variable.
    Number 314 in Lect. Notes in Math. Springer-Verlag, Berlin, 1973. MR 49:8970
  • [DW85] G. Dueck and H. C. Williams.
    Computation of the class number and class group of a complex cubic field.
    Mathematics of Computation, 45(171):223-231, 1985. MR 86m:11078
  • [JLW95] Michael J. Jacobson, Richard F. Lukes, and Hugh C. Williams.
    An investigation of bounds for the regulator of quadratic fields.
    Experimental Mathematics, 4(3):211-225, 1995. MR 97d:11173
  • [Kob88] N. Koblitz.
    Hyperelliptic cryptosystems.
    Journal of Cryptology, 1:139-150, 1988. MR 90k:11165
  • [KS99a] N. M. Katz and P. Sarnak.
    Random matrices, Frobenius eigenvalues and monodromy, volume 45 of AMS Colloquium Publications.
    AMS, Providence, Rhode Island, 1999. MR 2000b:11070
  • [KS99b] N. M. Katz and P. Sarnak.
    Zeroes of zeta functions and symmetry.
    Bulletin of the AMS, 36(1):1-26, January 1999. MR 2000f:11114
  • [Len82] H. W. Lenstra.
    On the calculation of regulators and class numbers of quadratic fields.
    London. Math. Soc. Lec. Note Ser., 56:123-150, 1982. MR 86g:11080
  • [LN83] R. Lidl and H. Niederreiter.
    Finite Fields.
    Addison-Wesley, Reading, MA, 1983. MR 86c:11106
  • [Lor96] D. Lorenzini.
    An invitation to arithmetic geometry, volume 9 of Graduate Studies in Mathematics.
    AMS, Providence, Rhode Island, 1996. MR 97e:14035
  • [MM80] M. L. Madan and D. J. Madden.
    On the theory of congruence function fields.
    Communications in Algebra, 8(17):1687-1697, 1980. MR 82b:12011
  • [MST99] V. Müller, A. Stein, and C. Thiel.
    Computing discrete logarithms in real quadratic congruence function fields of large genus.
    Mathematics of Computation, 68:807-822, 1999. MR 99i:11119
  • [Poo96] B. Poonen.
    Computational aspects of curves of genus at least $2$.
    In Algorithmic Number Theory Seminar ANTS-II, volume 1122 of Lecture Notes in Computer Science, pages 283-306. Springer, 1996. MR 98c:11059
  • [PR99] S. Paulus and H.-G. Rück.
    Real and imaginary quadratic representations of hyperelliptic function fields.
    Mathematics of Computation, 68:1233-1241, 1999. MR 99i:11107
  • [Sch31] F. K. Schmidt.
    Analytische Zahlentheorie in Körpern der Charakteristik $p$.
    Mathematische Zeitschrift, 33:1-32, 1931.
  • [Ser83] J. P. Serre.
    Sur le nombre des points rationnels d'une courbe algebrique sur un corps fini.
    C. R. Acad. Sci. Paris, 296:397-401, 1983. MR 85b:14027
  • [Ser99] J. P. Serre, 1999.
    Personal communications, Aug. 27, Aug. 28, Sept. 7, Sept. 11.
  • [SSW96] R. Scheidler, A. Stein, and H. C. Williams.
    Key-exchange in real quadratic congruence function fields.
    Designs, Codes and Cryptography, 7:153-174, 1996. MR 97d:94009
  • [STa] A. Stein and E. Teske.
    Optimized baby step-giant step methods and applications to hyperelliptic function fields.
    Unpublished manuscript.
  • [STb] A. Stein and E. Teske.
    The parallelized Pollard kangaroo method in real quadratic function fields.
    Math. Comp., posted on October 4, 2001, PII 50025-5718(01)01343-6 (to appear in print).
  • [Sti93] H. Stichtenoth.
    Algebraic Function Fields and Codes.
    Springer, Berlin, 1993. MR 94k:14016
  • [SW98] A. Stein and H. C. Williams.
    An improved method of computing the regulator of a real quadratic function field.
    In Algorithmic Number Theory Seminar ANTS-III, volume 1423 of Lecture Notes in Computer Science, pages 607-620. Springer, 1998. MR 2000j:11201
  • [SW99] A. Stein and H. C. Williams.
    Some methods for evaluating the regulator of a real quadratic function field.
    Experimental Mathematics, 8(2):119-133, 1999. MR 2000f:11152
  • [Tat65] J. Tate.
    Algebraic cycles and poles of zeta functions.
    In O. F. G. Schilling, editor, Arithmetical Algebraic Geometry, pages 93-110, New York, 1965. Harper & Row. MR 37:1371
  • [Wey68] H. Weyl.
    Gesammelte Abhandlungen, volume II.
    Springer-Verlag, Berlin, Heidelberg, New York, 1968. MR 37:6157
  • [WZ91] B. Weis and H. G. Zimmer.
    Artin's Theorie der quadratischen Kongruenzfunktionenkörper und ihre Anwendung auf die Berechnung der Einheiten- und Klassengruppen.
    Mitt. Math. Ges. Hamburg, Sond., XII(2), 1991. MR 93e:11141
  • [Yos73] H. Yoshida.
    On an analogue of the Sato conjecture.
    Inventiones mathematicae, 19:261-277, 1973. MR 49:2746
  • [Zha87] X. Zhang.
    Ambiguous classes and 2-rank of class groups of quadratic function fields.
    J. of China University of Science and Technology, 17(4):425-431, 1987. MR 89j:11115
  • [Zuc97] R. Zuccherato.
    The continued fraction algorithm and regulator for quadratic function fields of characteristic 2.
    Journal of Algebra, 190:563-587, 1997. MR 98a:11156

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y16, 11Y40, 11R29, 11R58, 11M38, 11R65

Retrieve articles in all journals with MSC (2000): 11Y16, 11Y40, 11R29, 11R58, 11M38, 11R65

Additional Information

Andreas Stein
Affiliation: University of Illinois at Urbana-Champaign, Department of Mathematics, 1409 West Green Street. Urbana, Illinois 61801

Edlyn Teske
Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1

Keywords: Hyperelliptic function field, class numbers, regulator, truncated Euler products
Received by editor(s): July 27, 1999
Received by editor(s) in revised form: August 2, 2000
Published electronically: October 4, 2001
Article copyright: © Copyright 2001 American Mathematical Society