Quadratic class numbers and character sums

Booker, Andrew

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

Quadratic class numbers and character sums
HTML articles powered by AMS MathViewer

by Andrew R. Booker PDF

Math. Comp. 75 (2006), 1481-1492 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) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
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
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/.