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

Dueck, G.; Williams, H. C.

doi:10.1090/S0025-5718-1985-0790655-4

Computation of the class number and class group of a complex cubic field
HTML articles powered by AMS MathViewer

by G. Dueck and H. C. Williams PDF

Math. Comp. 45 (1985), 223-231 Request permission

Corrigendum: Math. Comp. 50 (1988), 655-657.

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(|\Delta {|^{1/5 + \varepsilon }})$ elementary operations and G in $O(|\Delta {|^{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

B. N. Delone and D. K. Faddeev, The theory of irrationalities of the third degree, Translations of Mathematical Monographs, Vol. 10, American Mathematical Society, Providence, R.I., 1964. MR 0160744
H. Eisenbeis, G. Frey, and B. Ommerborn, Computation of the $2$-rank of pure cubic fields, Math. Comp. 32 (1978), no. 142, 559–569. MR 480416, DOI 10.1090/S0025-5718-1978-0480416-4
Veikko Ennola and Reino Turunen, On totally real cubic fields, Math. Comp. 44 (1985), no. 170, 495–518. MR 777281, DOI 10.1090/S0025-5718-1985-0777281-8
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
J. C. Lagarias and A. M. Odlyzko, Effective versions of the Chebotarev density theorem, Algebraic number fields: $L$-functions and Galois properties (Proc. Sympos., Univ. Durham, Durham, 1975) Academic Press, London, 1977, pp. 409–464. MR 0447191
J. C. Lagarias, H. L. Montgomery, and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), no. 3, 271–296. MR 553223, DOI 10.1007/BF01390234
R. Sherman Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646. MR 340163, DOI 10.1090/S0025-5718-1974-0340163-2
H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260

Astérisque

H. Zantema, Class numbers and units, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 213–234. MR 702518
Daniel Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969) Amer. Math. Soc., Providence, R.I., 1971, pp. 415–440. MR 0316385
Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the 1972 Number Theory Conference (Univ. Colorado, Boulder, Colo.), Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842

Concerning Algebraic Integers Derivable from a Root of an Equation of the Third Degree

On a Generalization of the Algorithm of Continued Fractions

H. C. Williams, G. W. Dueck, and B. K. Schmid, A rapid method of evaluating the regulator and class number of a pure cubic field, Math. Comp. 41 (1983), no. 163, 235–286. MR 701638, DOI 10.1090/S0025-5718-1983-0701638-2
Hugh C. Williams, Continued fractions and number-theoretic computations, Rocky Mountain J. Math. 15 (1985), no. 2, 621–655. Number theory (Winnipeg, Man., 1983). MR 823273, DOI 10.1216/RMJ-1985-15-2-621
H. C. Williams and C. R. Zarnke, Some algorithms for solving a cubic congruence modulo $p$, Utilitas Math. 6 (1974), 285–306. MR 389730