A fast, rigorous technique for computing the regulator of a real quadratic field
Roland de Haan, Melvin J. Jacobson, H. Williams · Mathematics of Computation · 2007
We present a new algorithm for computing the regulator of a real quadratic field Q ( D ) , \mathbb {Q}(\sqrt {D}), based on an algorithm for unconditionally verifying the correctness of the regulator produced by a subexponential algorithm, that runs in expected time O ( D 1 / 6 + ϵ ) O(D^{1/6 + \epsilon }) under the Generalized Riemann Hypothesis. The correctness of our algorithm relies on no unproven hypotheses and is currently the fastest known unconditional algorithm for computing the regulator. A number of implementation issues and performance enhancements are discussed, and we present the results of computations demonstrating the efficiency of the new algorithm.