On the infrastructure of the principal ideal class of an algebraic number field of unit rank one

Buchmann, Johannes; Williams, H. C.

doi:10.1090/S0025-5718-1988-0929554-6

On the infrastructure of the principal ideal class of an algebraic number field of unit rank one
HTML articles powered by AMS MathViewer

by Johannes Buchmann and H. C. Williams PDF

Math. Comp. 50 (1988), 569-579 Request permission

Abstract:

Let R be the regulator and let D be the absolute value of the discriminant of an order $\mathcal {O}$ of an algebraic number field of unit rank 1. It is shown how the infrastructure idea of Shanks can be used to decrease the number of binary operations needed to compute R from the best known $O(R{D^\varepsilon })$ for most continued fraction methods to $O({R^{1/2}}{D^\varepsilon })$. These ideas can also be applied to significantly decrease the number of operations needed to determine whether or not any fractional ideal of $\mathcal {O}$ is principal.

References

I. O. Angell, A table of complex cubic fields, Bull. London Math. Soc. 5 (1973), 37–38. MR 318099, DOI 10.1112/blms/5.1.37
Richard Brauer, On the zeta-functions of algebraic number fields, Amer. J. Math. 69 (1947), 243–250. MR 20597, DOI 10.2307/2371849

Congr. Numer.

Johannes Buchmann, Abschätzung der Periodenlänge einer verallgemeinerten Kettenbruchentwicklung, J. Reine Angew. Math. 361 (1985), 27–34 (German). MR 807249, DOI 10.1515/crll.1985.361.27
Johannes Buchmann, The computation of the fundamental unit of totally complex quartic orders, Math. Comp. 48 (1987), no. 177, 39–54. MR 866097, DOI 10.1090/S0025-5718-1987-0866097-1
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
Johannes Buchmann, On the period length of the generalized Lagrange algorithm, J. Number Theory 26 (1987), no. 1, 31–37. MR 883531, DOI 10.1016/0022-314X(87)90093-X
Johannes Buchmann and H. C. Williams, On principal ideal testing in totally complex quartic fields and the determination of certain cyclotomic constants, Math. Comp. 48 (1987), no. 177, 55–66. MR 866098, DOI 10.1090/S0025-5718-1987-0866098-3
Johannes Buchmann and H. C. Williams, On principal ideal testing in algebraic number fields, J. Symbolic Comput. 4 (1987), no. 1, 11–19. MR 908408, DOI 10.1016/S0747-7171(87)80049-4
M. D. Hendy, The distribution of ideal class numbers of real quadratic fields, Math. Comp. 29 (1975), no. 132, 1129–1134. MR 409402, DOI 10.1090/S0025-5718-1975-0409402-4

Mathematical Tables

Ravindran Kannan and Achim Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput. 8 (1979), no. 4, 499–507. MR 573842, DOI 10.1137/0208040

Lond. Math. Soc. Lecture Note Ser.

C. D. Patterson and H. C. Williams, Some periodic continued fractions with long periods, Math. Comp. 44 (1985), no. 170, 523–532. MR 777283, DOI 10.1090/S0025-5718-1985-0777283-1
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, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972) Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842
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, The spacing of the minima in certain cubic lattices, Pacific J. Math. 124 (1986), no. 2, 483–496. MR 856174
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
H. C. Williams, G. Cormack, and E. Seah, Calculation of the regulator of a pure cubic field, Math. Comp. 34 (1980), no. 150, 567–611. MR 559205, DOI 10.1090/S0025-5718-1980-0559205-7
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