Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Computations of class numbers
of real quadratic fields

Author: Anitha Srinivasan
Journal: Math. Comp. 67 (1998), 1285-1308
MSC (1991): Primary 11A51
MathSciNet review: 1468944
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11A51

Retrieve articles in all journals with MSC (1991): 11A51

Additional Information

Anitha Srinivasan
Affiliation: Department of Mathematics, University of Georgia, Athens, Georgia 30602
Address at time of publication: Department of Mathematics, University of Puerto Rico, CUH Station, 100 Carretera 908, Humacao, Puerto Rico 00791-4300

Keywords: Class number, binary quadratic forms, real quadratic field, regulator
Received by editor(s): July 2, 1996
Received by editor(s) in revised form: January 31, 1997
Article copyright: © Copyright 1998 American Mathematical Society