On principal ideal testing in totally complex quartic fields and the determination of certain cyclotomic constants
HTML articles powered by AMS MathViewer
- by Johannes Buchmann and H. C. Williams PDF
- Math. Comp. 48 (1987), 55-66 Request permission
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
-
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.
- K. K. Billevič, On the equivalence of two ideals in an algebraic field of order $n$, Mat. Sb. (N.S.) 58 (100) (1962), 17–28 (Russian). MR 0141652
- A. I. Borevich and I. R. Shafarevich, Number theory, Pure and Applied Mathematics, Vol. 20, Academic Press, New York-London, 1966. Translated from the Russian by Newcomb Greenleaf. MR 0195803
- 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, DOI 10.1007/BFb0032855 J. Buchmann, "On the computation of units and class numbers by a generalization of Lagrange’s algorithm," J. Number Theory. (To appear.)
- Johannes Buchmann, The computation of the fundamental unit of totally complex quartic orders, Math. Comp. 48 (1987), no. 177, 39–54. MR 866097, DOI 10.1090/S0025-5718-1987-0866097-1
- 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
- L. E. Dickson, Cyclotomy, Higher Congruences, and Waring’s Problem, Amer. J. Math. 57 (1935), no. 2, 391–424. MR 1507083, DOI 10.2307/2371217
- 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, DOI 10.1090/S0025-5718-1985-0790655-4
- 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, DOI 10.1090/S0025-5718-1985-0777278-8
- 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, DOI 10.1007/BF02579273
- Emma Lehmer, The quintic character of $2$ and $3$, Duke Math. J. 18 (1951), 11–18. MR 40338
- Emma Lehmer, On the location of Gauss sums, Math. Tables Aids Comput. 10 (1956), 194–202. MR 86092, DOI 10.1090/S0025-5718-1956-0086092-2
- Emma Lehmer, On the divisors of the discriminant of the period equation, Amer. J. Math. 90 (1968), 375–379. MR 227133, DOI 10.2307/2373534
- 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, DOI 10.1007/BF01457454
- 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
- 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
- H. W. Lenstra Jr., Integer programming with a fixed number of variables, Math. Oper. Res. 8 (1983), no. 4, 538–548. MR 727410, DOI 10.1287/moor.8.4.538
- 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, DOI 10.1515/crll.1985.361.50
- 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
- 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
- Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. MR 0371855 H. J. S. Smith, Report on the Theory of Numbers, Chelsea, New York, 1965.
- 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
- 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, DOI 10.1216/RMJ-1985-15-2-621
- Kenneth S. Williams, On Euler’s criterion for quintic nonresidues, Pacific J. Math. 61 (1975), no. 2, 543–550. MR 404113
- 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, DOI 10.1515/crll.1976.288.207
- Kenneth S. Williams, Explicit criteria for quintic residuacity, Math. Comp. 30 (1976), no. 136, 847–853. MR 412089, DOI 10.1090/S0025-5718-1976-0412089-9
Additional Information
- © Copyright 1987 American Mathematical Society
- 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