Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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
Email: as@turing.upr.clu.edu

DOI: http://dx.doi.org/10.1090/S0025-5718-98-00965-X
PII: S 0025-5718(98)00965-X
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