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), 679-688 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 Ford-Zassenhaus 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/0022-314X(87)90092-8 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/0022-314X(85)90055-1
- Carsten Eckhardt, Computation of class numbers by an analytic method, J. Symbolic Comput. 4 (1987), no. 1, 41–52. MR 908411, DOI 10.1016/S0747-7171(87)80052-4
- 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/S0025-5718-1985-0777278-8
- 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/S0747-7171(87)80054-8
- 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., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley 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/S0025-5718-1982-0637307-6 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. 165-167.
- 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 class-number one in certain real quadratic and pure cubic fields, Math. Comp. 46 (1986), no. 173, 333–336. MR 815853, DOI 10.1090/S0025-5718-1986-0815853-3
- 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/S0025-5718-1976-0414522-5
- 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), 679-688
- MSC: Primary 11R29; Secondary 11Y40
- DOI: https://doi.org/10.1090/S0025-5718-1989-0979937-4
- MathSciNet review: 979937