Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Computation of the class number and class group of a complex cubic field

Authors: G. Dueck and H. C. Williams
Journal: Math. Comp. 45 (1985), 223-231
MSC: Primary 11R16; Secondary 11R29, 11Y40
Corrigendum: Math. Comp. 50 (1988), 655-657.
MathSciNet review: 790655
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let h and G be, respectively, the class number and the class group of a complex cubic field of discriminant $ \Delta $. A method is described which makes use of recent ideas of Lenstra and Schoof to develop fast algorithms for finding h and G. Under certain Riemann hypotheses it is shown that these algorithms will compute h in $ O(\vert\Delta {\vert^{1/5 + \varepsilon }})$ elementary operations and G in $ O(\vert\Delta {\vert^{1/4 + \varepsilon }})$ elementary operations. Finally, the results of running some computer programs to determine h and G for all pure cubic fields $ \mathcal{Q}(\sqrt[3]{D})$, with $ 2 \leqslant D < 30,000$, are summarized.

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

  • [1] B. N. Delone & D. K. Faddeev, The Theory of Irrationalities of the Third Degree, Transl. Math. Monographs, Vol. 10, Amer. Math. Soc., Providence, R. I., 1964. MR 0160744 (28:3955)
  • [2] H. Eisenbeis, G. Frey & B. Ommerborn, "Computation of the 2-rank of pure cubic fields," Math. Comp., v. 32, 1978, pp. 559-569. MR 0480416 (58:579)
  • [3] V. Ennola & R. Turunen, "On totally real cubic fields," Math. Comp., v. 44, 1985, pp. 495-518. MR 777281 (86e:11100)
  • [4] D. E. Knuth, The Art of Computer Programming. Vol. II: Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [5] J. C. Lagarias & A. M. Odlyzko, "Effective versions of the Chebotarev density theorem," Algebraic Number Fields (A. Fröhlich, ed.), Academic Press, London, 1977, pp. 409-464. MR 0447191 (56:5506)
  • [6] J. C. Lagarias, H. L. Montgomery & A. M. Odlyzko, "A bound for the least prime ideal in the Chebotarev density theorem," Invent. Math., v. 54, 1979, pp. 271-296. MR 553223 (81b:12013)
  • [7] R. S. Lehman, "Factoring large integers," Math. Comp., v. 28, 1974, pp. 637-646. MR 0340163 (49:4919)
  • [8] H. W. Lenstra, Jr., On the Calculation of Regulators and Class Numbers of Quadratic Fields, London Math. Soc. Lecture Note Ser., Vol. 56, 1982, pp. 123-150. MR 697260 (86g:11080)
  • [9] 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.
  • [10] R. Schoof, "Quadratic fields and factorization," Computational Methods in Number Theory. Part II, Math. Centrum Tracts, No. 155, Amsterdam, 1983, pp. 235-286. MR 702519 (85g:11118b)
  • [11] D. Shanks, Class Number, A Theory of Factorization and Genera, Proc. Sympos. Pure Math., Vol. 20, Amer. Math. Soc., Providence, R. I., 1971, pp. 415-440. MR 0316385 (47:4932)
  • [12] D. Shanks, The Infrastructure of a Real Quadratic Field and Its Applications, Proc. 1972 Number Theory Conf. (Boulder, 1972), pp. 217-224. MR 0389842 (52:10672)
  • [13] G. F. Voronoi, Concerning Algebraic Integers Derivable from a Root of an Equation of the Third Degree, Master's Thesis, St. Petersburg, 1894. (Russian)
  • [14] G. F. Voronoi, On a Generalization of the Algorithm of Continued Fractions, Doctoral Dissertation, Warsaw, 1896. (Russian)
  • [15] H. C. Williams, G. W. Dueck & B. K. Schmid, "A rapid method of evaluating the regulator and class number of a pure cubic field," Math. Comp., v. 41, 1983, pp. 235-286. MR 701638 (84m:12010)
  • [16] H. C. Williams, "Continued fractions and number-theoretic computations," Proc. Number Theory Conf. (Edmonton, 1983); Rocky Mountain J. Math. (To appear.) MR 823273 (87h:11129)
  • [17] H. C. Williams & C. R. Zarnke, "Some algorithms for solving a cubic congruence modulo p," Utilitas Math., v. 6, 1974, pp. 285-306. MR 0389730 (52:10561)

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society