Small generators of the ideal class group
Authors:
Karim Belabas, Francisco Diaz y Diaz and Eduardo Friedman
Journal:
Math. Comp. 77 (2008), 1185-1197
MSC (2000):
Primary 11R04; Secondary 11R29
DOI:
https://doi.org/10.1090/S0025-5718-07-02003-0
Published electronically:
December 12, 2007
MathSciNet review:
2373197
Full-text PDF Free Access
Abstract | References | Similar Articles | Additional Information
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.
- Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI https://doi.org/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 https://doi.org/10.1016/0009-2614%2895%2901161-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
- 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 https://doi.org/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 https://doi.org/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
- Leo Murata, On the magnitude of the least prime primitive root, J. Number Theory 37 (1991), no. 1, 47–66. MR 1089789, DOI https://doi.org/10.1016/S0022-314X%2805%2980024-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 (French), 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 https://doi.org/10.1007/BF01394249
Retrieve articles in Mathematics of Computation with MSC (2000): 11R04, 11R29
Retrieve articles in all journals with MSC (2000): 11R04, 11R29
Additional 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
Keywords:
Ideal class group,
generalized Riemann hypothesis
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.
Article copyright:
© Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.