Explicit bounds and heuristics on class numbers in hyperelliptic function fields
HTML articles powered by AMS MathViewer
- by Andreas Stein and Edlyn Teske PDF
- Math. Comp. 71 (2002), 837-861 Request permission
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
- Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh Huang, A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 28–40. MR 1322708, DOI 10.1007/3-540-58691-1_{3}9
- E. Artin. Quadratische Körper im Gebiete der höheren Kongruenzen I, II. Math. Zeitschr., 19:153–206, 1924.
- Eric Bach, Improved approximations for Euler products, Number theory (Halifax, NS, 1994) CMS Conf. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13–28. MR 1353917, DOI 10.1016/0009-2614(95)01161-4
- B. J. Birch, How the number of points of an elliptic curve over a fixed prime field varies, J. London Math. Soc. 43 (1968), 57–60. MR 230682, DOI 10.1112/jlms/s1-43.1.57
- 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.
- J. W. S. Cassels and E. V. Flynn, Prolegomena to a middlebrow arithmetic of curves of genus $2$, London Mathematical Society Lecture Note Series, vol. 230, Cambridge University Press, Cambridge, 1996. MR 1406090, DOI 10.1017/CBO9780511526084
- Max Deuring, Lectures on the theory of algebraic functions of one variable, Lecture Notes in Mathematics, Vol. 314, Springer-Verlag, Berlin-New York, 1973. MR 0344231
- G. Dueck and H. C. Williams, Computation of the class number and class group of a complex cubic field, Math. Comp. 45 (1985), no. 171, 223–231. MR 790655, DOI 10.1090/S0025-5718-1985-0790655-4
- Michael J. Jacobson Jr., Richard F. Lukes, and Hugh C. Williams, An investigation of bounds for the regulator of quadratic fields, Experiment. Math. 4 (1995), no. 3, 211–225. MR 1387478
- Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, DOI 10.1007/BF02252872
- Nicholas M. Katz and Peter Sarnak, Random matrices, Frobenius eigenvalues, and monodromy, American Mathematical Society Colloquium Publications, vol. 45, American Mathematical Society, Providence, RI, 1999. MR 1659828, DOI 10.1090/coll/045
- Nicholas M. Katz and Peter Sarnak, Zeroes of zeta functions and symmetry, Bull. Amer. Math. Soc. (N.S.) 36 (1999), no. 1, 1–26. MR 1640151, DOI 10.1090/S0273-0979-99-00766-1
- 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
- Rudolf Lidl and Harald Niederreiter, Finite fields, Encyclopedia of Mathematics and its Applications, vol. 20, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1983. With a foreword by P. M. Cohn. MR 746963
- Dino Lorenzini, An invitation to arithmetic geometry, Graduate Studies in Mathematics, vol. 9, American Mathematical Society, Providence, RI, 1996. MR 1376367, DOI 10.1090/gsm/009
- Manohar L. Madan and Daniel J. Madden, On the theory of congruence function fields, Comm. Algebra 8 (1980), no. 17, 1687–1697. MR 585926, DOI 10.1080/00927878008822538
- Volker Müller, Andreas Stein, and Christoph Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus, Math. Comp. 68 (1999), no. 226, 807–822. MR 1620235, DOI 10.1090/S0025-5718-99-01040-6
- Bjorn Poonen, Computational aspects of curves of genus at least $2$, Algorithmic number theory (Talence, 1996) Lecture Notes in Comput. Sci., vol. 1122, Springer, Berlin, 1996, pp. 283–306. MR 1446520, DOI 10.1007/3-540-61581-4_{6}3
- Sachar Paulus and Hans-Georg Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68 (1999), no. 227, 1233–1241. MR 1627817, DOI 10.1090/S0025-5718-99-01066-2
- F. K. Schmidt. Analytische Zahlentheorie in Körpern der Charakteristik $p$. Mathematische Zeitschrift, 33:1–32, 1931.
- Jean-Pierre Serre, Sur le nombre des points rationnels d’une courbe algébrique sur un corps fini, C. R. Acad. Sci. Paris Sér. I Math. 296 (1983), no. 9, 397–402 (French, with English summary). MR 703906
- J. P. Serre, 1999. Personal communications, Aug. 27, Aug. 28, Sept. 7, Sept. 11.
- R. Scheidler, A. Stein, and Hugh C. Williams, Key-exchange in real quadratic congruence function fields, Des. Codes Cryptogr. 7 (1996), no. 1-2, 153–174. Special issue dedicated to Gustavus J. Simmons. MR 1377761, DOI 10.1007/BF00125081
- A. Stein and E. Teske. Optimized baby step–giant step methods and applications to hyperelliptic function fields. Unpublished manuscript.
- 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).
- Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
- Andreas Stein and Hugh C. Williams, An improved method of computing the regulator of a real quadratic function field, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 607–620. MR 1726105, DOI 10.1007/BFb0054896
- Andreas Stein and Hugh C. Williams, Some methods for evaluating the regulator of a real quadratic function field, Experiment. Math. 8 (1999), no. 2, 119–133. MR 1700574
- John T. Tate, Algebraic cycles and poles of zeta functions, Arithmetical Algebraic Geometry (Proc. Conf. Purdue Univ., 1963) Harper & Row, New York, 1965, pp. 93–110. MR 0225778
- Hermann Weyl, Gesammelte Abhandlungen. Bände I, II, III, IV, Springer-Verlag, Berlin-New York, 1968 (German). Herausgegeben von K. Chandrasekharan. MR 0230597
- Bosco Weis and Horst G. Zimmer, Artins Theorie der quadratischen Kongruenzfunktionenkörper und ihre Anwendung auf die Berechnung der Einheiten- und Klassengruppen, Mitt. Math. Ges. Hamburg 12 (1991), no. 2, 261–286 (German). Mathematische Wissenschaften gestern und heute. 300 Jahre Mathematische Gesellschaft in Hamburg, Teil 2. MR 1144788
- Hiroyuki Yoshida, On an analogue of the Sato conjecture, Invent. Math. 19 (1973), 261–277. MR 337977, DOI 10.1007/BF01425416
- Xian Ke Zhang, Ambiguous classes and $2$-rank of class group of quadratic function field, J. China Univ. Sci. Tech. 17 (1987), no. 4, 425–431 (English, with Chinese summary). MR 943934
- Robert J. Zuccherato, The continued fraction algorithm and regulator for quadratic function fields of characteristic $2$, J. Algebra 190 (1997), no. 2, 563–587. MR 1441964, DOI 10.1006/jabr.1996.6985
Additional Information
- Andreas Stein
- Affiliation: University of Illinois at Urbana-Champaign, Department of Mathematics, 1409 West Green Street. Urbana, Illinois 61801
- Email: andreas@math.uiuc.edu
- Edlyn Teske
- Affiliation: University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario, Canada N2L 3G1
- Email: eteske@math.uwaterloo.ca
- Received by editor(s): July 27, 1999
- Received by editor(s) in revised form: August 2, 2000
- Published electronically: October 4, 2001
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 837-861
- MSC (2000): Primary 11Y16, 11Y40, 11R29, 11R58; Secondary 11M38, 11R65
- DOI: https://doi.org/10.1090/S0025-5718-01-01385-0
- MathSciNet review: 1885633