Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Quadratic class numbers and character sums

Author: Andrew R. Booker
Journal: Math. Comp. 75 (2006), 1481-1492
MSC (2000): Primary 11Y35
Published electronically: March 21, 2006
MathSciNet review: 2219039
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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}(\vert d\vert^{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 [Enhancements On Off] (What's this?)

  • 1. A. O. L. Atkin and D. J. Bernstein.
    Prime sieves using binary quadratic forms.
    Math. Comp., 73(246):1023-1030 (electronic), 2004. MR 2031423 (2004i:11147)
  • 2. Ingrid Biehl and Johannes Buchmann.
    Algorithms for quadratic orders.
    In Mathematics of Computation 1943-1993: a half-century of computational mathematics (Vancouver, BC, 1993), volume 48 of Proc. Sympos. Appl. Math., pages 425-449. Amer. Math. Soc., Providence, RI, 1994. MR 1314882 (95m:11146)
  • 3. Andrew R. Booker and Andreas Strömbergsson.
    Numerical computations with the trace formula and the Selberg eigenvalue conjecture, Crelle (to appear).
  • 4. J. Buchmann.
    Algorithms for Binary Quadratic Forms.
    Springer-Verlag, to appear.
  • 5. J. Buchmann and S. Düllmann.
    A probabilistic class group and regulator algorithm and its implementation.
    In Computational number theory (Debrecen, 1989), pages 53-72. de Gruyter, Berlin, 1991. MR 1151855 (92m:11150)
  • 6. Johannes Buchmann.
    A subexponential algorithm for the determination of class groups and regulators of algebraic number fields.
    In Séminaire de Théorie des Nombres, Paris 1988-1989, volume 91 of Progr. Math., pages 27-41. Birkhäuser Boston, Boston, MA, 1990. MR 1104698 (92g:11125)
  • 7. Johannes Buchmann and Stephan Düllmann.
    Distributed class group computation.
    In Informatik, volume 1 of Teubner-Texte Inform., pages 69-79. Teubner, Stuttgart, 1992. MR 1182565 (93e:11153)
  • 8. Johannes Buchmann, Michael J. Jacobson, Jr., Stefan Neis, Patrick Theobald, and Damian Weber.
    Sieving methods for class group computation.
    In Algorithmic algebra and number theory (Heidelberg, 1997), pages 3-10. Springer, Berlin, 1999. MR 1672089 (2000a:11177)
  • 9. Johannes Buchmann, Michael J. Jacobson, Jr., and Edlyn Teske.
    On some computational problems in finite abelian groups.
    Math. Comp., 66(220):1663-1687, 1997. MR 1432126 (98a:11185)
  • 10. D. A. Burgess.
    The distribution of quadratic residues and non-residues.
    Mathematika, 4:106-112, 1957. MR 0093504 (20:28)
  • 11. 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.
    In Séminaire de Théorie des Nombres, Paris, 1990-91, volume 108 of Progr. Math., pages 35-46. Birkhäuser Boston, Boston, MA, 1993. MR 1263522 (94m:11151)
  • 12. H. Cohen and H. W. Lenstra, Jr.
    Heuristics on class groups of number fields.
    In Number theory, Noordwijkerhout 1983 (Noordwijkerhout, 1983), volume 1068 of Lecture Notes in Math., pages 33-62. Springer, Berlin, 1984. MR 0756082 (85j:11144)
  • 13. Henri Cohen.
    A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics.
    Springer-Verlag, Berlin, 1993. MR 1228206 (94i:11105)
  • 14. 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.
  • 15. P. Dusart.
    Autour de la fonction qui compte le nombre de nombres premiers.
    Université de Limoges, Ph.D. thesis, 1998.
  • 16. E. Grosswald.
    On Burgess' bound for primitive roots modulo primes and an application to $ \Gamma (p)$.
    Amer. J. Math., 103(6):1171-1183, 1981. MR 0636957 (82k:10059)
  • 17. James L. Hafner and Kevin S. McCurley.
    A rigorous subexponential algorithm for computation of class groups.
    J. Amer. Math. Soc., 2(4):837-850, 1989. MR 1002631 (91f:11090)
  • 18. H. A. Helfgott and A. Venkatesh.
    Integral points on elliptic curves and $ 3$-torsion in class groups.
    preprint, 2004.
  • 19. Henryk Iwaniec and Emmanuel Kowalski.
    Analytic number theory, volume 53 of American Mathematical Society Colloquium Publications.
    American Mathematical Society, Providence, RI, 2004. MR 2061214 (2005h:11005)
  • 20. Michael J. Jacobson, Jr., Renate Scheidler, and Hugh C. Williams.
    The efficiency and security of a real quadratic field based key exchange protocol.
    In Public-key cryptography and computational number theory (Warsaw, 2000), pages 89-112. de Gruyter, Berlin, 2001. MR 1881630 (2003f:94062)
  • 21. Chun-Gang Ji and Hong-Wen Lu.
    Lower bound of real primitive $ L$-function at $ s=1$.
    Acta Arith., 111(4):405-409, 2004. MR 2039505 (2004k:11140)
  • 22. A. K. Lenstra and H. W. Lenstra, Jr.
    Algorithms in number theory.
    Tech. Report 97-008, 1987.
  • 23. A. K. Lenstra and H. W. Lenstra, Jr.
    Algorithms in number theory.
    In Handbook of theoretical computer science, Vol. A, pages 673-715. Elsevier, Amsterdam, 1990. MR 1127178
  • 24. H. W. Lenstra, Jr.
    On the calculation of regulators and class numbers of quadratic fields.
    In Number theory days, 1980 (Exeter, 1980), volume 56 of London Math. Soc. Lecture Note Ser., pages 123-150. Cambridge Univ. Press, Cambridge, 1982. MR 0697260 (86g:11080)
  • 25. J.E. Littlewood.
    On the class number of the corpus $ p(\sqrt{-k})$.
    Proc. London Math. Soc., 27:358-372, 1928.
  • 26. Stéphane Louboutin.
    Computation of class numbers of quadratic number fields.
    Math. Comp., 71(240):1735-1743 (electronic), 2002. MR 1933052 (2003i:11163)
  • 27. K. S. McCurley.
    Cryptographic key distribution and computation in class groups.
    In Proceedings NATO ASI on Number Theory and Applications (Dordrecht), volume 265 of ASI Series C, pages 459-479. Kluwer, 1989. MR 1123090 (92e:11149)
  • 28. L. B. Pierce.
    The $ 3$-part of class numbers of quadratic fields.
    Oxford University, MSc. thesis, 2004.
  • 29. J. Barkley Rosser and Lowell Schoenfeld.
    Approximate formulas for some functions of prime numbers.
    Illinois J. Math., 6:64-94, 1962. MR 0137689 (25:1139)
  • 30. Daniel Shanks.
    Class number, a theory of factorization, and genera.
    In 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969), pages 415-440. Amer. Math. Soc., Providence, R.I., 1971. MR 0316385 (47:4932)
  • 31. Daniel Shanks.
    The infrastructure of a real quadratic field and its applications.
    In Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), pages 217-224, Boulder, Colo., 1972. Univ. Colorado. MR 0389842 (52:10672)
  • 32. Anitha Srinivasan.
    Computations of class numbers of real quadratic fields.
    Math. Comp., 67(223):1285-1308, 1998. MR 1468944 (99b:11143)
  • 33. The PARI Group, Bordeaux.
    PARI/GP tutorial, 2004.
    available from
  • 34. The PARI Group, Bordeaux.
    PARI/GP, version 2.1.5, 2004.
    available from

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y35

Retrieve articles in all journals with MSC (2000): 11Y35

Additional Information

Andrew R. Booker
Affiliation: Department of Mathematics, 530 Church Street, University of Michigan, Ann Arbor, Michigan 48109

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
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society