Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 

 

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 $ \cl$ of a number field $ K$ can be generated by the prime ideals of $ K$ having norm smaller than $ 12\big(\log\abs{\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 [Enhancements On Off] (What's this?)


Similar Articles

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
Email: friedman@uchile.cl

DOI: https://doi.org/10.1090/S0025-5718-07-02003-0
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.