Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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 $ \mathcal{L}$ be any totally complex quartic field. Two algorithms are described for determining whether or not any given ideal in $ \mathcal{L}$ 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 $ p \equiv 1\;\pmod 5$. Given any quadratic (or quintic) nonresidue of p, it is shown that these cyclotomic numbers can be efficiently computed in $ O({(\log p)^3})$ binary operations.


References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society