Small generators of the ideal class group

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.