On the computation of the class number of an algebraic number field
HTML articles powered by AMS MathViewer
 by Johannes Buchmann and H. C. Williams PDF
 Math. Comp. 53 (1989), 679688 Request permission
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

R. Böffgen, "Der Algorithmus von FordZassenhaus zur Berechnung von Ganzheitsbasen in Polynomalgebren," Ann. Univ. Sarav. Math.Natur. Fak., v. 1, 1987.
 Johannes Buchmann, On the computation of units and class numbers by a generalization of Lagrange’s algorithm, J. Number Theory 26 (1987), no. 1, 8–30. MR 883530, DOI 10.1016/0022314X(87)900928 J. Buchmann, Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper, Habilitationsschrift, Düsseldorf, 1987.
 Explicit methods in number theory, Oberwolfach Rep. 4 (2007), no. 3, 1957–2034. Abstracts from the workshop held July 15–21, 2007; Organized by Henri Cohen, Hendrik W. Lenstra and Don B. Zagier; Oberwolfach Reports. Vol. 4, no. 3. MR 2432111, DOI 10.4171/OWR/2007/34
 Gary Cornell and Lawrence C. Washington, Class numbers of cyclotomic fields, J. Number Theory 21 (1985), no. 3, 260–274. MR 814005, DOI 10.1016/0022314X(85)900551
 Carsten Eckhardt, Computation of class numbers by an analytic method, J. Symbolic Comput. 4 (1987), no. 1, 41–52. MR 908411, DOI 10.1016/S07477171(87)800524
 U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), no. 170, 463–471. MR 777278, DOI 10.1090/S00255718198507772788
 David J. Ford, The construction of maximal orders over a Dedekind domain, J. Symbolic Comput. 4 (1987), no. 1, 69–75. MR 908413, DOI 10.1016/S07477171(87)800548
 Larry C. Grove, Algebra, Pure and Applied Mathematics, vol. 110, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1983. MR 734306
 G. H. Hardy and E. M. Wright, An introduction to the theory of numbers, Oxford, at the Clarendon Press, 1954. 3rd ed. MR 0067125
 Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., AddisonWesley Series in Computer Science and Information Processing, AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
 Michael Pohst and Hans Zassenhaus, On effective computation of fundamental units. I, Math. Comp. 38 (1982), no. 157, 275–291. MR 637307, DOI 10.1090/S00255718198206373076 J. Oesterlé, "Versions effectives du théorème de Chebotarev sous l’hypothèse de Riemann généralisée," Astérisque, v. 61, 1979, pp. 165167.
 Carl Ludwig Siegel, Abschätzung von Einheiten, Nachr. Akad. Wiss. Göttingen Math.Phys. Kl. II 1969 (1969), 71–86 (German). MR 249395
 M. Tennenhouse and H. C. Williams, A note on classnumber one in certain real quadratic and pure cubic fields, Math. Comp. 46 (1986), no. 173, 333–336. MR 815853, DOI 10.1090/S00255718198608158533
 H. C. Williams and J. Broere, A computational technique for evaluating $L(1,\chi )$ and the class number of a real quadratic field, Math. Comp. 30 (1976), no. 136, 887–893. MR 414522, DOI 10.1090/S00255718197604145225
 Aurel Wintner, A factorization of the densities of the ideals in algebraic number fields, Amer. J. Math. 68 (1946), 273–284. MR 15423, DOI 10.2307/2371839
Additional Information
 © Copyright 1989 American Mathematical Society
 Journal: Math. Comp. 53 (1989), 679688
 MSC: Primary 11R29; Secondary 11Y40
 DOI: https://doi.org/10.1090/S00255718198909799374
 MathSciNet review: 979937