A rigorous subexponential algorithm for computation of class groups

Abstract

Let C(−d) denote the Gauss Class Group of quadratic forms of a negative discriminant −d (or equivalently, the class group of the imaginary quadratic field Q(Equation presented)). We give a rigorous proof that there exists a Las Vegas algorithm that will compute the structure of C(−d) with an expected running time of (Equation presented) bit operations, where (Equation presented). Thus, of course, also includes the computation of the class number h(−d), the cardinality of C(−d). © 1989 American Mathematical Society.