Small generators of the ideal class group
HTML articles powered by AMS MathViewer
- by Karim Belabas, Francisco Diaz y Diaz and Eduardo Friedman;
- Math. Comp. 77 (2008), 1185-1197
- DOI: https://doi.org/10.1090/S0025-5718-07-02003-0
- Published electronically: December 12, 2007
- PDF | 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
Bibliographic Information
- Karim Belabas
- Affiliation: Université Bordeaux I, IMB–UMR 5251, 351 cours de la Libération, F-33405 Talence cedex, France
- Email: Karim.Belabas@math.u-bordeaux.fr
- Francisco Diaz y Diaz
- Affiliation: Université Bordeaux I, IMB–UMR 5251, 351 cours de la Libération, F-33405 Talence cedex, France
- Email: diaz@math.u-bordeaux1.fr
- Eduardo Friedman
- Affiliation: Departamento de Matemática, Universidad de Chile, Casilla 653, Santiago, Chile
- MR Author ID: 69455
- Email: friedman@uchile.cl
- Received by editor(s): December 5, 2005
- Published electronically: December 12, 2007
- Additional Notes: This work was partially supported by Chilean Fondecyt grant no. 1040585.
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 77 (2008), 1185-1197
- MSC (2000): Primary 11R04; Secondary 11R29
- DOI: https://doi.org/10.1090/S0025-5718-07-02003-0
- MathSciNet review: 2373197