Explicit bounds and heuristics on class numbers in hyperelliptic function fields

Stein, Andreas; Teske, Edlyn

doi:10.1090/S0025-5718-01-01385-0

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