Explicit bounds and heuristics on class numbers in hyperelliptic function fields

Stein, Andreas; Teske, Edlyn

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

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
Posted: October 4, 2001
MathSciNet review: 1885633
Full-text PDF Free Access

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 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.

[ADH94] 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 (96b:11078), http://dx.doi.org/10.1007/3-540-58691-1_39
[Art24] E. Artin.
Quadratische Körper im Gebiete der höheren Kongruenzen I, II.
Math. Zeitschr., 19:153-206, 1924.
[Bac95] 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 (96i:11124)
[Bir68] 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 0230682 (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, London Mathematical Society Lecture Note Series, vol. 230, Cambridge University Press, Cambridge, 1996. MR 1406090 (97i:11071)
[Deu73] Max Deuring, Lectures on the theory of algebraic functions of one variable, Lecture Notes in Mathematics, Vol. 314, Springer-Verlag, Berlin, 1973. MR 0344231 (49 #8970)
[DW85] 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 (86m:11078), http://dx.doi.org/10.1090/S0025-5718-1985-0790655-4
[JLW95] 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 (97d:11173)
[Kob88] Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215 (90k:11165), http://dx.doi.org/10.1007/BF02252872
[KS99a] 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 (2000b:11070)
[KS99b] 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 (2000f:11114), http://dx.doi.org/10.1090/S0273-0979-99-00766-1
[Len82] 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)
[LN83] 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 (86c:11106)
[Lor96] Dino Lorenzini, An invitation to arithmetic geometry, Graduate Studies in Mathematics, vol. 9, American Mathematical Society, Providence, RI, 1996. MR 1376367 (97e:14035)
[MM80] Manohar L. Madan and Daniel J. Madden, On the theory of congruence function fields, Comm. Algebra 8 (1980), no. 17, 1687–1697. MR 585926 (82b:12011), http://dx.doi.org/10.1080/00927878008822538
[MST99] 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 (99i:11119), http://dx.doi.org/10.1090/S0025-5718-99-01040-6
[Poo96] 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 (98c:11059), http://dx.doi.org/10.1007/3-540-61581-4_63
[PR99] 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 (99i:11107), http://dx.doi.org/10.1090/S0025-5718-99-01066-2
[Sch31] F. K. Schmidt.
Analytische Zahlentheorie in Körpern der Charakteristik .
Mathematische Zeitschrift, 33:1-32, 1931.
[Ser83] 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 (85b:14027)
[Ser99] J. P. Serre, 1999.
Personal communications, Aug. 27, Aug. 28, Sept. 7, Sept. 11.
[SSW96] 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 (97d:94009), http://dx.doi.org/10.1007/BF00125081
[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] Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961 (94k:14016)
[SW98] 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 (2000j:11201), http://dx.doi.org/10.1007/BFb0054896
[SW99] 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 (2000f:11152)
[Tat65] 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 (37 #1371)
[Wey68] Hermann Weyl, Gesammelte Abhandlungen. Bände I, II, III, IV, Herausgegeben von K. Chandrasekharan, Springer-Verlag, Berlin, 1968 (German). MR 0230597 (37 #6157)
[WZ91] 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 (93e:11141)
[Yos73] Hiroyuki Yoshida, On an analogue of the Sato conjecture, Invent. Math. 19 (1973), 261–277. MR 0337977 (49 #2746)
[Zha87] 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 (89j:11115)
[Zuc97] 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 (98a:11156), http://dx.doi.org/10.1006/jabr.1996.6985

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|