Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On the computation of the class number of an algebraic number field

Authors: Johannes Buchmann and H. C. Williams
Journal: Math. Comp. 53 (1989), 679-688
MSC: Primary 11R29; Secondary 11Y40
MathSciNet review: 979937
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: It is shown how the analytic class number formula can be used to produce an algorithm which efficiently computes the class number h of an algebraic number field F. The method assumes the truth of the Generalized Riemann Hypothesis in order to estimate the residue of the Dedekind zeta function of F at $s = 1$ sufficiently well that h can be determined unambiguously. Given the regulator R of F and a known divisor ${h^ \ast }$ of h, it is shown that this technique will produce the value of h in $O(|{d_F}{|^{1 + \varepsilon }}/{({h^ \ast }R)^2})$ elementary operations, where ${d_F}$ is the discriminant of F. Thus, if $h < |{d_F}{|^{1/8}}$, then the complexity of computing h (with ${h^ \ast } = 1$) is $O(|{d_F}{|^{1/4 + \varepsilon }})$.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11R29, 11Y40

Retrieve articles in all journals with MSC: 11R29, 11Y40

Additional Information

Article copyright: © Copyright 1989 American Mathematical Society