Quadratic class numbers and character sums

Booker, Andrew

doi:10.1090/S0025-5718-06-01850-3

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
Posted: 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 . 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 (2004), no. 246, 1023–1030 (electronic). MR 2031423 (2004i:11147), http://dx.doi.org/10.1090/S0025-5718-03-01501-1
2. Ingrid Biehl and Johannes Buchmann, Algorithms for quadratic orders, mathematics (Vancouver, BC, 1993) Proc. Sympos. Appl. Math., vol. 48, Amer. Math. Soc., Providence, RI, 1994, pp. 425–449. 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, Computational number theory (Debrecen, 1989) de Gruyter, Berlin, 1991, pp. 53–72. MR 1151855 (92m:11150)
6. 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 (92g:11125)
7. Johannes Buchmann and Stephan Düllmann, Distributed class group computation, Informatik, Teubner-Texte Inform., vol. 1, Teubner, Stuttgart, 1992, pp. 69–79. MR 1182565 (93e:11153)
8. 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 (2000a:11177)
9. 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 (98a:11185), http://dx.doi.org/10.1090/S0025-5718-97-00880-6
10. D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. 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, 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 (94m:11151)
12. 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 (85j:11144), http://dx.doi.org/10.1007/BFb0099440
13. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, 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 Γ(𝑝), Amer. J. Math. 103 (1981), no. 6, 1171–1183. MR 636957 (82k:10059), http://dx.doi.org/10.2307/2374229
17. 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 (91f:11090), http://dx.doi.org/10.1090/S0894-0347-1989-1002631-0
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, American Mathematical Society Colloquium Publications, vol. 53, 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, Public-key cryptography and computational number theory (Warsaw, 2000), de Gruyter, Berlin, 2001, pp. 89–112. MR 1881630 (2003f:94062)
21. Chun-Gang Ji and Hong-Wen Lu, Lower bound of real primitive 𝐿-function at 𝑠=1, Acta Arith. 111 (2004), no. 4, 405–409. MR 2039505 (2004k:11140), http://dx.doi.org/10.4064/aa111-4-2
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, Handbook of theoretical computer science, Vol. A, Elsevier, Amsterdam, 1990, pp. 673–715. MR 1127178
24. 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)
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 (2002), no. 240, 1735–1743. MR 1933052 (2003i:11163), http://dx.doi.org/10.1090/S0025-5718-01-01367-9
27. 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 (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 (1962), 64–94. MR 0137689 (25 #1139)
30. 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), Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385 (47 #4932)
31. Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842 (52 #10672)
32. Anitha Srinivasan, Computations of class numbers of real quadratic fields, Math. Comp. 67 (1998), no. 223, 1285–1308. MR 1468944 (99b:11143), http://dx.doi.org/10.1090/S0025-5718-98-00965-X
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/.

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