Computations of class numbers of real quadratic fields

In this paper an unconditional probabilistic algorithm to compute the class number of a real quadratic field is presented, which computes the class number in expected time . 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 . Previous algorithms with the above running time , obtain an approximation for by assuming an appropriate extension of the Riemann Hypothesis. Our algorithm finds an appoximation for 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 . However, our estimate of on the running time of our algorithm to compute the class number is not effective.