Improvements in the computation of ideal class groups of imaginary quadratic number fields (Q540359)

The author describes practical improvements to the index-calculus algorithm for computing the ideal class group of an imaginary quadratic number field. The relation generation stage is improved via the incorporation of the double large prime improvement to relation generation (originally proposed for integer factorization algorithms). The more complicated relations obtained, as well as the larger extended factor base, are handled via improvements to the linear algebra step, including a version of structured Gaussian elimination for reducing the matrix dimensions that was designed for this particular algorithm, and the incorporation of \textit{U. Vollmer's} Hermite normal form algorithm [``A note on the Hermite basis computation of large integer matrices'', in: J. R. Sendra (ed.), ISSAC 2003. Proceedings of the 2003 international symposium on symbolic and algebraic computation, Philadelphia, PA, USA, August 3--6, 2003. New York, NY: ACM Press. 255--257 (2003; Zbl 1072.68701)]. The latter is based on solving linear systems over \(\mathbb{Z}\) and is designed to be efficient when the number of non-zero diagonal elements of the output is small, which is frequently the case for class group computation. Numerical results demonstrate improved performance for sufficiently large discriminants, and the class group of a field with \(110\) decimal digit discriminant is computed for the first time, the current record as of the time of writing this review.