Mathematics of Computation

Author(s): Andrew R. Booker.
Journal: Math. Comp. 75 (2006), 1481-1492.
MSC (2000): Primary 11Y35
Posted: March 21, 2006
Retrieve article in: PDF DVI PostScript

Abstract: We present an algorithm for computing the class number of the quadratic number field of discriminant

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

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 -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 -function at .
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 -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 http://pari.math.u-bordeaux.fr/doc.html.
34.: The PARI Group, Bordeaux.
PARI/GP, version 2.1.5, 2004.
available from http://pari.math.u-bordeaux.fr/.

Andrew R. Booker
Affiliation: Department of Mathematics, 530 Church Street, University of Michigan, Ann Arbor, Michigan 48109
Email: arbooker@umich.edu

DOI: 10.1090/S0025-5718-06-01850-3
PII: S 0025-5718(06)01850-3
Received by editor(s): November 26, 2004
Received by editor(s) in revised form: July 21, 2005
Posted: March 21, 2006
Additional Notes: The author was supported by an NSF postdoctoral fellowship
Copyright of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS