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), 569579
MSC:
Primary 11R11; Secondary 11R16, 11R27, 11Y16, 11Y40
MathSciNet review:
929554
Fulltext 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 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 for most continued fraction methods to . These ideas can also be applied to significantly decrease the number of operations needed to determine whether or not any fractional ideal of is principal.
 [1]
I.
O. Angell, A table of complex cubic fields, Bull. London Math.
Soc. 5 (1973), 37–38. MR 0318099
(47 #6648)
 [2]
Richard
Brauer, On the zetafunctions of algebraic number fields,
Amer. J. Math. 69 (1947), 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. 312.
 [4]
Johannes
Buchmann, Abschätzung der Periodenlänge einer
verallgemeinerten Kettenbruchentwicklung, J. Reine Angew. Math.
361 (1985), 27–34 (German). MR 807249
(87b:11011), http://dx.doi.org/10.1515/crll.1985.361.27
 [5]
Johannes
Buchmann, The computation of the fundamental
unit of totally complex quartic orders, Math.
Comp. 48 (1987), no. 177, 39–54. MR 866097
(87m:11126), http://dx.doi.org/10.1090/S00255718198708660971
 [6]
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
(89b:11104), http://dx.doi.org/10.1016/0022314X(87)900928
 [7]
Johannes
Buchmann, On the period length of the generalized Lagrange
algorithm, J. Number Theory 26 (1987), no. 1,
31–37. MR
883531 (88g:11078), http://dx.doi.org/10.1016/0022314X(87)90093X
 [8]
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
(87m:11127), http://dx.doi.org/10.1090/S00255718198708660983
 [9]
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 (88m:11093), http://dx.doi.org/10.1016/S07477171(87)800494
 [10]
M.
D. Hendy, The distribution of ideal class
numbers of real quadratic fields, Math.
Comp. 29 (1975), no. 132, 1129–1134. MR 0409402
(53 #13157), http://dx.doi.org/10.1090/S00255718197504094024
 [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]
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
(81k:15002), http://dx.doi.org/10.1137/0208040
 [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. 123150.
 [14]
C.
D. Patterson and H.
C. Williams, Some periodic continued fractions with
long periods, Math. Comp.
44 (1985), no. 170, 523–532. MR 777283
(86h:11113), http://dx.doi.org/10.1090/S00255718198507772831
 [15]
R.
J. Schoof, Quadratic fields and factorization, Computational
methods in number theory, Part II, Math. Centre Tracts, vol. 155,
Math. Centrum, Amsterdam, 1982, pp. 235–286. MR 702519
(85g:11118b)
 [16]
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
(52 #10672)
 [17]
Hugh
C. Williams, Continued fractions and numbertheoretic
computations, Rocky Mountain J. Math. 15 (1985),
no. 2, 621–655. Number theory (Winnipeg, Man., 1983). MR 823273
(87h:11129), http://dx.doi.org/10.1216/RMJ1985152621
 [18]
H.
C. Williams, The spacing of the minima in certain cubic
lattices, Pacific J. Math. 124 (1986), no. 2,
483–496. MR
856174 (87i:11152)
 [19]
H.
C. Williams and J.
Broere, A computational technique for
evaluating 𝐿(1,𝜒) and the class number of a real quadratic
field, Math. Comp. 30
(1976), no. 136, 887–893. MR 0414522
(54 #2623), http://dx.doi.org/10.1090/S00255718197604145225
 [20]
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
(81d:12003), http://dx.doi.org/10.1090/S00255718198005592057
 [21]
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
(84m:12010), http://dx.doi.org/10.1090/S00255718198307016382
 [1]
 I. O. Angell, "A table of complex cubic fields," Bull. London Math. Soc., v. 5, 1973, pp. 3738. MR 0318099 (47:6648)
 [2]
 R. Brauer, "On the zetafunctions of algebraic number fields," Amer. J. Math., v. 69, 1947, pp. 243250. MR 0020597 (8:567h)
 [3]
 D. A. Buell, "Computer computation of class groups in quadratic number fields," Congr. Numer., v. 22, 1978, pp. 312.
 [4]
 J. Buchmann, "Abschätzung der Periodenlänge einer verallgemeinerten Kettenbruchentwicklung," J. Reine Angew. Math., v. 361, 1985, pp. 2734. 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. 3954. 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. 830. MR 883530 (89b:11104)
 [7]
 J. Buchmann, "On the period length of the generalized Lagrange algorithm," J. Number Theory, v. 26, 1987, pp. 3137. 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. 5566. 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. 1119. MR 908408 (88m:11093)
 [10]
 M. D. Hendy, "The distribution of ideal class numbers of real quadratic fields," Math. Comp., v. 29, 1975, pp. 11291134. 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. 499507. 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. 123150.
 [14]
 C. D. Patterson & H. C. Williams, "Some periodic continued fractions with long periods," Math. Comp., v. 44, 1985, pp. 523532. 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. 235286. MR 702519 (85g:11118b)
 [16]
 D. Shanks, The Infrastructure of Real Quadratic Fields and Its Applications, Proc. 1972 Number Theory Conf., Boulder, 1972, pp. 217224. MR 0389842 (52:10672)
 [17]
 H. C. Williams, "Continued fractions and numbertheoretic computations," Rocky Mountain J. Math., v. 15, 1985, pp. 621655. MR 823273 (87h:11129)
 [18]
 H. C. Williams, "The spacing of the minima in certain cubic lattices," Pacific J. Math., v. 124, 1986, pp. 483496. MR 856174 (87i:11152)
 [19]
 H. C. Williams & J. Broere, "A computational technique for evaluating and the class number of a real quadratic field," Math. Comp., v. 30, 1976, pp. 887893. 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. 567611. 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. 235286. 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
DOI:
http://dx.doi.org/10.1090/S00255718198809295546
PII:
S 00255718(1988)09295546
Article copyright:
© Copyright 1988
American Mathematical Society
