Small generators of the ideal class group

Belabas, Karim; Diaz y Diaz, Francisco; Friedman, Eduardo

doi:10.1090/S0025-5718-07-02003-0

Small generators of the ideal class group
HTML articles powered by AMS MathViewer

by Karim Belabas, Francisco Diaz y Diaz and Eduardo Friedman PDF

Math. Comp. 77 (2008), 1185-1197 Request permission

Abstract:

Assuming the Generalized Riemann Hypothesis, Bach has shown that the ideal class group $\mathcal {C}\ell _{K}$ of a number field $K$ can be generated by the prime ideals of $K$ having norm smaller than $12\big (\log |\mathrm {Discriminant}(K)|\big )^2$. This result is essential for the computation of the class group and units of $K$ by Buchmann’s algorithm, currently the fastest known. However, once $\mathcal {C}\ell _K$ has been computed, one notices that this bound could have been replaced by a much smaller value, and so much work could have been saved. We introduce here a short algorithm which allows us to reduce Bach’s bound substantially, usually by a factor 20 or so. The bound produced by the algorithm is asymptotically worse than Bach’s, but favorable constants make it useful in practice.

References

Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
Eric Bach, Improved approximations for Euler products, Number theory (Halifax, NS, 1994) CMS Conf. Proc., vol. 15, Amer. Math. Soc., Providence, RI, 1995, pp. 13–28. MR 1353917, DOI 10.1016/0009-2614(95)01161-4
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
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
Ana-Cecilia de la Maza, Bounds for the smallest norm in an ideal class, Math. Comp. 71 (2002), no. 240, 1745–1758. MR 1933053, DOI 10.1090/S0025-5718-01-01373-4
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
Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723, DOI 10.1007/978-1-4612-0853-2
Leo Murata, On the magnitude of the least prime primitive root, J. Number Theory 37 (1991), no. 1, 47–66. MR 1089789, DOI 10.1016/S0022-314X(05)80024-1
Number fields database, Bordeaux, available at ftp://megrez.math.u-bordeaux.fr/pub/numberfields.
PARI/GP, version 2.2.10, Bordeaux, 2005, http://pari.math.u-bordeaux.fr/.
Georges Poitou, Sur les petits discriminants, Séminaire Delange-Pisot-Poitou, 18e année: 1976/77, Théorie des nombres, Fasc. 1, Secrétariat Math., Paris, 1977, pp. Exp. No. 6, 18 (French). MR 551335
André Weil, Sur les “formules explicites” de la théorie des nombres premiers, Comm. Sém. Math. Univ. Lund [Medd. Lunds Univ. Mat. Sem.] 1952 (1952), no. Tome Supplémentaire, 252–265 (French). MR 53152
Rainer Zimmert, Ideale kleiner Norm in Idealklassen und eine Regulatorabschätzung, Invent. Math. 62 (1981), no. 3, 367–380 (German). MR 604833, DOI 10.1007/BF01394249