Computations of class numbers of real quadratic fields

Abstract:

In this paper an unconditional probabilistic algorithm to compute the class number of a real quadratic field $\mathbb {Q}(\sqrt {d})$ is presented, which computes the class number in expected time $O(d^{1/5+\epsilon })$. The algorithm is a random version of Shanks’ algorithm. One of the main steps in algorithms to compute the class number is the approximation of $L(1, \chi )$. Previous algorithms with the above running time $O(d^{1/5+\epsilon })$, obtain an approximation for $L(1, \chi )$ by assuming an appropriate extension of the Riemann Hypothesis. Our algorithm finds an appoximation for $L(1, \chi )$ without assuming the Riemann Hypothesis, by using a new technique that we call the ‘Random Summation Technique’. As a result, we are able to compute the regulator deterministically in expected time $O(d^{1/5+\epsilon })$. However, our estimate of $O(d^{1/5+\epsilon })$ on the running time of our algorithm to compute the class number is not effective.