Quadratic class numbers and character sums
HTML articles powered by AMS MathViewer
- by Andrew R. Booker;
- Math. Comp. 75 (2006), 1481-1492
- DOI: https://doi.org/10.1090/S0025-5718-06-01850-3
- Published electronically: March 21, 2006
- PDF | Request permission
Abstract:
We present an algorithm for computing the class number of the quadratic number field of discriminant $d$. The algorithm terminates unconditionally with the correct answer and, under the GRH, executes in $O_{\varepsilon }(|d|^{1/4+\varepsilon })$ steps. The technique used combines algebraic methods with Burgess’ theorem on character sums to estimate $L(1,\chi _d)$. We give an explicit version of Burgess’ theorem valid for prime discriminants and, as an application, we compute the class number of a 32-digit discriminant.References
- A. O. L. Atkin and D. J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), no. 246, 1023–1030. MR 2031423, DOI 10.1090/S0025-5718-03-01501-1
- Ingrid Biehl and Johannes Buchmann, Algorithms for quadratic orders, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993) Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994, pp. 425–449. MR 1314882, DOI 10.1090/psapm/048/1314882
- Andrew R. Booker and Andreas Strömbergsson. Numerical computations with the trace formula and the Selberg eigenvalue conjecture, Crelle (to appear).
- J. Buchmann. Algorithms for Binary Quadratic Forms. Springer-Verlag, to appear.
- J. Buchmann and S. Düllmann, A probabilistic class group and regulator algorithm and its implementation, Computational number theory (Debrecen, 1989) de Gruyter, Berlin, 1991, pp. 53–72. MR 1151855
- Johannes Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27–41. MR 1104698
- Johannes Buchmann and Stephan Düllmann, Distributed class group computation, Informatik, Teubner-Texte Inform., vol. 1, Teubner, Stuttgart, 1992, pp. 69–79. MR 1182565, DOI 10.1007/978-3-322-95233-2_{5}
- Johannes Buchmann, Michael J. Jacobson Jr., Stefan Neis, Patrick Theobald, and Damian Weber, Sieving methods for class group computation, Algorithmic algebra and number theory (Heidelberg, 1997) Springer, Berlin, 1999, pp. 3–10. MR 1672089
- Johannes Buchmann, Michael J. Jacobson Jr., and Edlyn Teske, On some computational problems in finite abelian groups, Math. Comp. 66 (1997), no. 220, 1663–1687. MR 1432126, DOI 10.1090/S0025-5718-97-00880-6
- D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 93504, DOI 10.1112/S0025579300001157
- H. Cohen, F. Diaz y Diaz, and M. Olivier, Calculs de nombres de classes et de régulateurs de corps quadratiques en temps sous-exponentiel, Séminaire de Théorie des Nombres, Paris, 1990–91, Progr. Math., vol. 108, Birkhäuser Boston, Boston, MA, 1993, pp. 35–46 (French). MR 1263522
- H. Cohen and H. W. Lenstra Jr., Heuristics on class groups of number fields, Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983) Lecture Notes in Math., vol. 1068, Springer, Berlin, 1984, pp. 33–62. MR 756082, DOI 10.1007/BFb0099440
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- R. De Haan, M. J. Jacobson, Jr., and H. C. Williams. A fast, rigorous technique for verifying the regulator of a real quadratic field. preprint, 2004.
- P. Dusart. Autour de la fonction qui compte le nombre de nombres premiers. Université de Limoges, Ph.D. thesis, 1998.
- E. Grosswald, On Burgess’ bound for primitive roots modulo primes and an application to $\Gamma (p)$, Amer. J. Math. 103 (1981), no. 6, 1171–1183. MR 636957, DOI 10.2307/2374229
- James L. Hafner and Kevin S. McCurley, A rigorous subexponential algorithm for computation of class groups, J. Amer. Math. Soc. 2 (1989), no. 4, 837–850. MR 1002631, DOI 10.1090/S0894-0347-1989-1002631-0
- H. A. Helfgott and A. Venkatesh. Integral points on elliptic curves and $3$-torsion in class groups. preprint, 2004.
- Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214, DOI 10.1090/coll/053
- Michael J. Jacobson Jr., Renate Scheidler, and Hugh C. Williams, The efficiency and security of a real quadratic field based key exchange protocol, Public-key cryptography and computational number theory (Warsaw, 2000) de Gruyter, Berlin, 2001, pp. 89–112. MR 1881630
- Chun-Gang Ji and Hong-Wen Lu, Lower bound of real primitive $L$-function at $s=1$, Acta Arith. 111 (2004), no. 4, 405–409. MR 2039505, DOI 10.4064/aa111-4-2
- A. K. Lenstra and H. W. Lenstra, Jr. Algorithms in number theory. Tech. Report 97-008, 1987.
- A. K. Lenstra and H. W. Lenstra Jr., Algorithms in number theory, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR 1127178
- 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
- J.E. Littlewood. On the class number of the corpus $p(\sqrt {-k})$. Proc. London Math. Soc., 27:358–372, 1928.
- Stéphane Louboutin, Computation of class numbers of quadratic number fields, Math. Comp. 71 (2002), no. 240, 1735–1743. MR 1933052, DOI 10.1090/S0025-5718-01-01367-9
- Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459–479. MR 1123090
- L. B. Pierce. The $3$-part of class numbers of quadratic fields. Oxford University, MSc. thesis, 2004.
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Proc. Sympos. Pure Math., Vol. XX, Amer. Math. Soc., Providence, RI, 1971, pp. 415–440. MR 316385
- Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the 1972 Number Theory Conference (Univ. Colorado, Boulder, Colo.), University of Colorado, Boulder, CO, 1972, pp. 217–224. MR 389842
- Anitha Srinivasan, Computations of class numbers of real quadratic fields, Math. Comp. 67 (1998), no. 223, 1285–1308. MR 1468944, DOI 10.1090/S0025-5718-98-00965-X
- The PARI Group, Bordeaux. PARI/GP tutorial, 2004. available from http://pari.math.u-bordeaux.fr/doc.html.
- The PARI Group, Bordeaux. PARI/GP, version 2.1.5, 2004. available from http://pari.math.u-bordeaux.fr/.
Bibliographic Information
- Andrew R. Booker
- Affiliation: Department of Mathematics, 530 Church Street, University of Michigan, Ann Arbor, Michigan 48109
- Email: arbooker@umich.edu
- Received by editor(s): November 26, 2004
- Received by editor(s) in revised form: July 21, 2005
- Published electronically: March 21, 2006
- Additional Notes: The author was supported by an NSF postdoctoral fellowship
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 75 (2006), 1481-1492
- MSC (2000): Primary 11Y35
- DOI: https://doi.org/10.1090/S0025-5718-06-01850-3
- MathSciNet review: 2219039