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

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(\vert{d_F}{\vert^{1 + \varepsilon }}/{({h^ \ast }R)^2})$ elementary operations, where $ {d_F}$ is the discriminant of F. Thus, if $ h < \vert{d_F}{\vert^{1/8}}$, then the complexity of computing h (with $ {h^ \ast } = 1$) is $ O(\vert{d_F}{\vert^{1/4 + \varepsilon }})$.

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

  • [1] R. Böffgen, "Der Algorithmus von Ford-Zassenhaus zur Berechnung von Ganzheitsbasen in Polynomalgebren," Ann. Univ. Sarav. Math.-Natur. Fak., v. 1, 1987.
  • [2] J. Buchmann, "On the computation of units and class numbers by a generalization of Lagrange's algorithm," J. Number Theory, v. 26, 1987, pp. 8-30. MR 883530 (89b:11104)
  • [3] J. Buchmann, Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper, Habilitationsschrift, Düsseldorf, 1987.
  • [4] J. Buchmann & H. W. Lenstra, Jr. (To appear). MR 2432111
  • [5] G. Cornell & L. C. Washington, "Class numbers of cyclotomic fields," J. Number Theory, v. 21, 1985, pp. 260-274. MR 814005 (87d:11079)
  • [6] C. Eckhardt, "Computation of class numbers by an analytic method," J. Symb. Comput., v. 4, 1987, pp. 41-52. MR 908411 (89b:11089)
  • [7] U. Fincke & M. Pohst, "Improved methods for calculating vectors of short length in a lattice, including a complexity analysis," Math. Comp., v. 44, 1985, pp. 463-471. MR 777278 (86e:11050)
  • [8] D. Ford, "The construction of maximal orders over a Dedekind domain," J. Symb. Comput., v. 4, 1987, pp. 71-77. MR 908413 (89a:11121)
  • [9] L. C. Grove, Algebra, Academic Press, New York, 1983. MR 734306 (86j:00002)
  • [10] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, 3rd ed., Oxford Univ. Press, Oxford, 1954. MR 0067125 (16:673c)
  • [11] D. E. Knuth, The Art of Computer Programming, Vol. II: Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [12] M. Pohst, P. Weiler & H. Zassenhaus, "On effective computation of fundamental units. II," Math. Comp., v. 38, 1982, pp. 293-329. MR 637308 (83e:12005b)
  • [13] 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.
  • [14] C. L. Siegel, "Abschätzung von Einheiten," Nachr. Akad. Wiss. Göttingen II: Math.-Phys. Kl., 1969, pp. 71-86. MR 0249395 (40:2640)
  • [15] M. Tennenhouse & H. C. Williams, "A note on class-number one in certain real quadratic and pure cubic fields," Math. Comp., v. 46, 1986, pp. 333-336. MR 815853 (87b:11127)
  • [16] H. C. Williams & J. Broere, "A computational technique for evaluating $ L(1,\chi )$ and the class number of a real quadratic field," Math. Comp., v. 30, 1976, pp. 887-893. MR 0414522 (54:2623)
  • [17] A. Wintner, "A factorization of the densities of ideals in algebraic number fields," Amer. J. Math., v. 68, 1946, pp. 273-284. MR 0015423 (7:416b)

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

American Mathematical Society