A rigorous subexponential algorithm for computation of class groups

Source abstract

Let C ( − d ) C( - d) denote the Gauss Class Group of quadratic forms of a negative discriminant − d - d (or equivalently, the class group of the imaginary quadratic field Q ( − d ) Q(\sqrt { - d} ) ). We give a rigorous proof that there exists a Las Vegas algorithm that will compute the structure of C ( − d ) C( - d) with an expected running time of L ( d ) 2 + o ( 1 ) L{(d)^{\sqrt 2 + o(1)}} bit operations, where L ( d ) = exp ( log d log log d ) L(d) = {\text {exp}}(\sqrt {\log \,d\;\log \,\log \,d} ) . Thus, of course, also includes the computation of the class number h ( − d ) h( - d) , the cardinality of C ( − d ) C( - d) .