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

Buchmann, Johannes; Williams, H. C.

doi:10.1090/S0025-5718-1987-0866098-3

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 Free Access

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.

[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. Billevič, On the equivalence of two ideals in an algebraic field of order 𝑛, Mat. Sb. (N.S.) 58 (100) (1962), 17–28 (Russian). MR 0141652
[3] A. I. Borevich and I. R. Shafarevich, Number theory, Translated from the Russian by Newcomb Greenleaf. Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966. MR 0195803
[4] Johannes Buchmann, A criterion for the equivalence of two ideals, EUROSAM 84 (Cambridge, 1984) Lecture Notes in Comput. Sci., vol. 174, Springer, Berlin, 1984, pp. 333–340. MR 779138, https://doi.org/10.1007/BFb0032855
[5] J. Buchmann, "On the computation of units and class numbers by a generalization of Lagrange's algorithm," J. Number Theory. (To appear.)
[6] Johannes Buchmann, The computation of the fundamental unit of totally complex quartic orders, Math. Comp. 48 (1987), no. 177, 39–54. MR 866097, https://doi.org/10.1090/S0025-5718-1987-0866097-1
[7] B. N. Delone and D. K. Faddeev, The theory of irrationalities of the third degree, Translations of Mathematical Monographs, Vol. 10, American Mathematical Society, Providence, R.I., 1964. MR 0160744
[8] L. E. Dickson, Cyclotomy, Higher Congruences, and Waring’s Problem, Amer. J. Math. 57 (1935), no. 2, 391–424. MR 1507083, https://doi.org/10.2307/2371217
[9] G. Dueck and H. C. Williams, Computation of the class number and class group of a complex cubic field, Math. Comp. 45 (1985), no. 171, 223–231. MR 790655, https://doi.org/10.1090/S0025-5718-1985-0790655-4
[10] U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comp. 44 (1985), no. 170, 463–471. MR 777278, https://doi.org/10.1090/S0025-5718-1985-0777278-8
[11] M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1 (1981), no. 2, 169–197. MR 625550, https://doi.org/10.1007/BF02579273
[12] Emma Lehmer, The quintic character of 2 and 3, Duke Math. J. 18 (1951), 11–18. MR 40338
[13] Emma Lehmer, On the location of Gauss sums, Math. Tables Aids Comput. 10 (1956), 194–202. MR 86092, https://doi.org/10.1090/S0025-5718-1956-0086092-2
[14] Emma Lehmer, On the divisors of the discriminant of the period equation, Amer. J. Math. 90 (1968), 375–379. MR 227133, https://doi.org/10.2307/2373534
[15] A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515–534. MR 682664, https://doi.org/10.1007/BF01457454
[16] H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
[17] H. W. Lenstra Jr., Primality testing, Computational methods in number theory, Part I, Math. Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982, pp. 55–77. MR 700258
[18] H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8 (1983), no. 4, 538–548. MR 727410, https://doi.org/10.1287/moor.8.4.538
[19] Michael Pohst and Hans Zassenhaus, Über die Berechnung von Klassenzahlen und Klassengruppen algebraischer Zahlkörper, J. Reine Angew. Math. 361 (1985), 50–72 (German). MR 807252, https://doi.org/10.1515/crll.1985.361.50
[20] 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
[21] 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
[22] Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
[23] H. J. S. Smith, Report on the Theory of Numbers, Chelsea, New York, 1965.
[24] Albert Leon Whiteman, The cyclotomic numbers of order ten, Proc. Sympos. Appl. Math., Vol. 10, American Mathematical Society, Providence, R.I., 1960, pp. 95–111. MR 0113851
[25] 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, https://doi.org/10.1216/RMJ-1985-15-2-621
[26] Kenneth S. Williams, On Euler’s criterion for quintic nonresidues, Pacific J. Math. 61 (1975), no. 2, 543–550. MR 404113
[27] Kenneth S. Williams, Explicit forms of Kummer’s complementary theorems to his law of quintic reciprocity, J. Reine Angew. Math. 288 (1976), 207–210. MR 424652, https://doi.org/10.1515/crll.1976.288.207
[28] Kenneth S. Williams, Explicit criteria for quintic residuacity, Math. Comp. 30 (1976), no. 136, 847–853. MR 412089, https://doi.org/10.1090/S0025-5718-1976-0412089-9