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), 5566
MSC:
Primary 11Y40; Secondary 11R16
MathSciNet review:
866098
Fulltext PDF Free Access
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. 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
(25 #5049)
 [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, 1966. MR 0195803
(33 #4001)
 [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
(86h:11094), http://dx.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
(87m:11126), http://dx.doi.org/10.1090/S00255718198708660971
 [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
(28 #3955)
 [8]
L.
E. Dickson, Cyclotomy, Higher Congruences, and Waring’s
Problem, Amer. J. Math. 57 (1935), no. 2,
391–424. MR
1507083, http://dx.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
(86m:11078), http://dx.doi.org/10.1090/S00255718198507906554
 [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
(86e:11050), http://dx.doi.org/10.1090/S00255718198507772788
 [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
(84a:90044), http://dx.doi.org/10.1007/BF02579273
 [12]
Emma
Lehmer, The quintic character of 2 and 3, Duke Math. J.
18 (1951), 11–18. MR 0040338
(12,677a)
 [13]
Emma
Lehmer, On the location of Gauss
sums, Math. Tables Aids Comput. 10 (1956), 194–202. MR 0086092
(19,123a), http://dx.doi.org/10.1090/S00255718195600860922
 [14]
Emma
Lehmer, On the divisors of the discriminant of the period
equation, Amer. J. Math. 90 (1968), 375–379. MR 0227133
(37 #2718)
 [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 (84a:12002), http://dx.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
(86g:11080)
 [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
(85g:11117)
 [18]
H.
W. Lenstra Jr., Integer programming with a fixed number of
variables, Math. Oper. Res. 8 (1983), no. 4,
538–548. MR
727410 (86f:90106), http://dx.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
(87g:11147), http://dx.doi.org/10.1515/crll.1985.361.50
 [20]
R.
J. Schoof, Quadratic fields and factorization, Computational
methods in number theory, Part II, Math. Centre Tracts, vol. 155,
Math. Centrum, Amsterdam, 1982, pp. 235–286. MR 702519
(85g:11118b)
 [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
(52 #10672)
 [22]
Daniel
Shanks, Five numbertheoretic algorithms, (Univ. Manitoba,
Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973,
pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
(51 #8072)
 [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
(22 #4682)
 [25]
Hugh
C. Williams, Continued fractions and numbertheoretic
computations, Rocky Mountain J. Math. 15 (1985),
no. 2, 621–655. Number theory (Winnipeg, Man., 1983). MR 823273
(87h:11129), http://dx.doi.org/10.1216/RMJ1985152621
 [26]
Kenneth
S. Williams, On Euler’s criterion for quintic
nonresidues, Pacific J. Math. 61 (1975), no. 2,
543–550. MR 0404113
(53 #7917)
 [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 0424652
(54 #12611)
 [28]
Kenneth
S. Williams, Explicit criteria for quintic
residuacity, Math. Comp.
30 (1976), no. 136, 847–853. MR 0412089
(54 #218), http://dx.doi.org/10.1090/S00255718197604120899
 [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. 1728. 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. 333340. 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. 3954. 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. 391424. 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. 223231. 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. 463471. 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. 169197. MR 625550 (84a:90044)
 [12]
 Emma Lehmer, "The quintic character of 2 and 3," Duke Math. J., v. 18, 1951, pp. 1118. MR 0040338 (12:677a)
 [13]
 Emma Lehmer, "On the location of Gauss sums," M.T.A.C., v. 10, 1956, pp. 194202. MR 0086092 (19:123a)
 [14]
 Emma Lehmer, "On the divisors of the discriminant of the period equation," Amer. J. Math., v. 90, 1968, pp. 375379. 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. 515534. 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. 123150. 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. 5577. MR 700258 (85g:11117)
 [18]
 H. W. Lenstra, Jr., "Integer programming with a fixed number of variables," Math. Oper. Res., v. 8, 1983, pp. 538548. 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. 5072. 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. 235286. 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. 217224. 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. 5170. 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 numbertheoretic computations," Rocky Mountain J. Math., v. 15, 1985, pp. 621655. MR 823273 (87h:11129)
 [26]
 K. S. Williams, "On Euler's criterion for quintic nonresidues," Pacific J. Math., v. 61, 1975, pp. 543550. 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. 207210. MR 0424652 (54:12611)
 [28]
 K. S. Williams, "Explicit criteria for quintic residuacity," Math. Comp., v. 30, 1976, pp. 847853. 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:
http://dx.doi.org/10.1090/S00255718198708660983
PII:
S 00255718(1987)08660983
Article copyright:
© Copyright 1987 American Mathematical Society
