Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



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

Authors: Johannes Buchmann and H. C. Williams
Journal: Math. Comp. 50 (1988), 569-579
MSC: Primary 11R11; Secondary 11R16, 11R27, 11Y16, 11Y40
MathSciNet review: 929554
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] I. O. Angell, "A table of complex cubic fields," Bull. London Math. Soc., v. 5, 1973, pp. 37-38. MR 0318099 (47:6648)
  • [2] R. Brauer, "On the zeta-functions of algebraic number fields," Amer. J. Math., v. 69, 1947, pp. 243-250. MR 0020597 (8:567h)
  • [3] D. A. Buell, "Computer computation of class groups in quadratic number fields," Congr. Numer., v. 22, 1978, pp. 3-12.
  • [4] J. Buchmann, "Abschätzung der Periodenlänge einer verallgemeinerten Kettenbruchentwicklung," J. Reine Angew. Math., v. 361, 1985, pp. 27-34. MR 807249 (87b:11011)
  • [5] J. Buchmann, "On the computation of the fundamental unit of totally complex quartic orders," Math. Comp., v. 48, 1987, pp. 39-54. MR 866097 (87m:11126)
  • [6] 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)
  • [7] J. Buchmann, "On the period length of the generalized Lagrange algorithm," J. Number Theory, v. 26, 1987, pp. 31-37. MR 883531 (88g:11078)
  • [8] J. Buchmann & H. C. Williams, "On principal ideal testing in totally complex quartic fields and the determination of certain cyclotomic constants," Math. Comp., v. 48, 1987, pp. 55-66. MR 866098 (87m:11127)
  • [9] J. Buchmann & H. C. Williams, "On principal ideal testing in algebraic number fields," J. Symb. Comput., v. 4, 1987, pp. 11-19. MR 908408 (88m:11093)
  • [10] M. D. Hendy, "The distribution of ideal class numbers of real quadratic fields," Math. Comp., v. 29, 1975, pp. 1129-1134. MR 0409402 (53:13157)
  • [11] E. L. Ince, "Cycles of reduced ideals in quadratic fields," Mathematical Tables, Vol. IV, British Association for the Advancement of Science, London, 1934.
  • [12] R. Kannan & A. Bachem, "Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix," SIAM J. Comput., v. 8, 1979, pp. 499-507. MR 573842 (81k:15002)
  • [13] H. W. Lenstra, Jr., "On the calculation of class numbers and regulators of quadratic fields," Lond. Math. Soc. Lecture Note Ser., v. 56, 1982, pp. 123-150.
  • [14] C. D. Patterson & H. C. Williams, "Some periodic continued fractions with long periods," Math. Comp., v. 44, 1985, pp. 523-532. MR 777283 (86h:11113)
  • [15] R. J. Schoof, "Quadratic fields and factorization," in Computational Methods in Number Theory (H. W. Lenstra, Jr. and R. Tijdemann, eds.), Math. Centrum Tracts, Number 155, Part II, Amsterdam, 1982, pp. 235-286. MR 702519 (85g:11118b)
  • [16] D. Shanks, The Infrastructure of Real Quadratic Fields and Its Applications, Proc. 1972 Number Theory Conf., Boulder, 1972, pp. 217-224. MR 0389842 (52:10672)
  • [17] H. C. Williams, "Continued fractions and number-theoretic computations," Rocky Mountain J. Math., v. 15, 1985, pp. 621-655. MR 823273 (87h:11129)
  • [18] H. C. Williams, "The spacing of the minima in certain cubic lattices," Pacific J. Math., v. 124, 1986, pp. 483-496. MR 856174 (87i:11152)
  • [19] 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)
  • [20] H. C. Williams, G. Cormack & E. Seah, "Calculation of the regulator of a pure cubic field," Math. Comp., v. 34, 1980, pp. 567-611. MR 559205 (81d:12003)
  • [21] 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)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11R11, 11R16, 11R27, 11Y16, 11Y40

Retrieve articles in all journals with MSC: 11R11, 11R16, 11R27, 11Y16, 11Y40

Additional Information

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society