On principal ideal testing in totally complex quartic fields and the determination of certain cyclotomic constants

Authors:
Johannes Buchmann and H. C. Williams

Journal:
Math. Comp. **48** (1987), 55-66

MSC:
Primary 11Y40; Secondary 11R16

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866098-3

MathSciNet review:
866098

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let be any totally complex quartic field. Two algorithms are described for determining whether or not any given ideal in is principal. One of these algorithms is very efficient in practice, but its complexity is difficult to analyze; the other algorithm is computationally more elaborate but, in this case, a complexity analysis can be provided.

These ideas are applied to the problem of determining the cyclotomic numbers of order 5 for a prime . Given any quadratic (or quintic) nonresidue of *p*, it is shown that these cyclotomic numbers can be efficiently computed in binary operations.

**[1]**Eric Bach,*What to Do Until the Witness Comes*:*Explicit Bounds for Primality Testing and Related Problems*, Ph.D. Thesis, Univ. of California, Berkeley, Calif., 1984.**[2]**K. K. Billevich, "On the equivalence of two ideals in an algebraic number field of order*n*,"*Mat. Sb.*(*N.S.*), v. 58 (100), 1962, pp. 17-28. MR**0141652 (25:5049)****[3]**Z. I. Borevich & I. R. Shafarevich,*Number Theory*, Academic Press, New York, 1966. MR**0195803 (33:4001)****[4]**J. Buchmann, "A criterion for the equivalence of two ideals," in*EUROSAM 84 Proceedings*, Lecture Notes in Comput. Sci., vol. 174, 1984, pp. 333-340. MR**779138 (86h:11094)****[5]**J. Buchmann, "On the computation of units and class numbers by a generalization of Lagrange's algorithm,"*J. Number Theory*. (To appear.)**[6]**J. Buchmann, "The computation of the fundamental unit of totally complex quartic orders,"*Math. Comp.*, v. 48, 1987, pp. 39-54. MR**866097 (87m:11126)****[7]**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)****[8]**L. E. Dickson, "Cyclotomy, higher congruences, and Waring's problem,"*Amer. J. Math.*, v. 57, 1935, pp. 391-424. MR**1507083****[9]**G. Dueck & H. C. Williams, "Computation of the class number and class group of a complex cubic field,"*Math. Comp.*, v. 45, 1985, pp. 223-231. MR**790655 (86m:11078)****[10]**U. Fincke & M. Pohst, "Improved methods for calculating vectors of short length in a lattice, including a complexity analysis,"*Math. Comp.*, v. 44, 1985, pp. 463-471. MR**777278 (86e:11050)****[11]**M. Grötschel, L. Lovász & A. Schrijver, "The ellipsoid method and its consequences in combinatorial optimization,"*Combinatorica*, v. 1, 1981, pp. 169-197. MR**625550 (84a:90044)****[12]**Emma Lehmer, "The quintic character of 2 and 3,"*Duke Math. J.*, v. 18, 1951, pp. 11-18. MR**0040338 (12:677a)****[13]**Emma Lehmer, "On the location of Gauss sums,"*M.T.A.C.*, v. 10, 1956, pp. 194-202. MR**0086092 (19:123a)****[14]**Emma Lehmer, "On the divisors of the discriminant of the period equation,"*Amer. J. Math.*, v. 90, 1968, pp. 375-379. MR**0227133 (37:2718)****[15]**A. K. Lenstra, H. W. Lenstra, Jr. & L. Lovász, "Factoring polynomials with rational coefficients,"*Math. Ann.*, v. 261, 1982, pp. 515-534. MR**682664 (84a:12002)****[16]**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)****[17]**H. W. Lenstra, Jr., "Primality testing,"*Computational Methods in Number Theory*, Math. Centrum Tracts, Number 154, part I, Amsterdam, 1983, pp. 55-77. MR**700258 (85g:11117)****[18]**H. W. Lenstra, Jr., "Integer programming with a fixed number of variables,"*Math. Oper. Res.*, v. 8, 1983, pp. 538-548. MR**727410 (86f:90106)****[19]**M. Pohst & H. Zassenhaus, "Über die Berechnung von Klassenzahlen und Klassengruppen algebraischer Zahlkörper,*J. Reine Angew. Math.*, v. 361, 1985, pp. 50-72. MR**807252 (87g:11147)****[20]**R. J. Schoof, "Quadratic fields and factorization,"*Computational Methods in Number Theory*, Math. Centrum Tracts, Number 155, part II, Amsterdam, 1983, pp. 235-286. MR**702519 (85g:11118b)****[21]**D. Shanks, "The infrastructure of real quadratic fields and its application,"*Proc. 1972 Number Theory Conf.*, Boulder, Colorado, 1973, pp. 217-224. MR**0389842 (52:10672)****[22]**D. Shanks, "Five number theoretic algorithms,"*Proc. Second Manitoba Conference on Numerical Mathematics*(Univ. of Manitoba, Winnipeg, Man., 1972),*Congressus Numerantium*, VII, Utilitas Math., Winnipeg, Manitoba, 1973, pp. 51-70. MR**0371855 (51:8072)****[23]**H. J. S. Smith,*Report on the Theory of Numbers*, Chelsea, New York, 1965.**[24]**A. L. Whiteman,*The Cyclotomic Numbers of Order Ten*, Proc. Sympos. Appl. Math., vol. 10, Amer. Math. Soc., Providence, R. I., 1960. MR**0113851 (22:4682)****[25]**H. C. Williams, "Continued fractions and number-theoretic computations,"*Rocky Mountain J. Math.*, v. 15, 1985, pp. 621-655. MR**823273 (87h:11129)****[26]**K. S. Williams, "On Euler's criterion for quintic nonresidues,"*Pacific J. Math.*, v. 61, 1975, pp. 543-550. MR**0404113 (53:7917)****[27]**K. S. Williams, "Explicit forms of Kummer's complementary theorems to his law of quintic reciprocity,"*J. Reine Angew. Math.*, v. 288, 1976, pp. 207-210. MR**0424652 (54:12611)****[28]**K. S. Williams, "Explicit criteria for quintic residuacity,"*Math. Comp.*, v. 30, 1976, pp. 847-853. MR**0412089 (54:218)**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866098-3

Article copyright:
© Copyright 1987
American Mathematical Society