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

What to Do Until the Witness Comes

Explicit Bounds for Primality Testing and Related Problems

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. Number Theory

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

Report on the Theory of Numbers

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