Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

Computing greatest common divisors and factorizations in quadratic number fields


Authors: Erich Kaltofen and Heinrich Rolletschek
Journal: Math. Comp. 53 (1989), 697-720
MSC: Primary 11Y40; Secondary 11R11, 11R27, 11Y16
DOI: https://doi.org/10.1090/S0025-5718-1989-0982367-2
MathSciNet review: 982367
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In a quadratic number field $ {\mathbf{Q}}(\sqrt D )$, D a squarefree integer, with class number 1, any algebraic integer can be decomposed uniquely into primes, but for only 21 domains Euclidean algorithms are known. It was shown by Cohn [5] that for $ D \leq - 19$ even remainder sequences with possibly nondecreasing norms cannot determine the GCD of arbitrary inputs. We extend this result by showing that there does not even exist an input in these domains for which the GCD computation becomes possible by allowing nondecreasing norms or remainders whose norms are not as small as possible. We then provide two algorithms for computing the GCD of algebraic integers in quadratic number fields $ {\mathbf{Q}}(\sqrt D )$. The first applies only to complex quadratic number fields with class number 1, and is based on a short vector construction in a lattice. Its complexity is $ O({S^3})$, where S is the number of bits needed to encode the input. The second algorithm allows us to compute GCD's of algebraic integers in arbitrary number fields (ideal GCD's if the class number is $ > 1$). It requires only $ O({S^2})$ binary steps for fixed D, but works poorly if D is large. Finally, we prove that in any domain, the computation of the prime factorization of an algebraic integer can be reduced in polynomial time to the problem of factoring its norm into rational primes. Our reduction is based on a constructive version of a theorem by A. Thue.


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

  • [1] E. S. Barnes & H. P. F. Swinnerton-Dyer, "The homogeneous minima of binary quadratic forms," Acta Math., v. 87, 1952, pp. 255-323. MR 0053162 (14:730a)
  • [2] A. Brauer & R. L. Reynolds, "On a theorem of Aubry-Thue", Canad. J. Math., v. 3, 1951, pp. 367-374. MR 0048487 (14:21a)
  • [3] B. F. Caviness & G. E. Collins, Algorithms for Gaussian Integer Arithmetic, Proc. 1976 ACM Symp. Symbolic Algebraic Comp., 1976, pp. 36-45.
  • [4] H. Chatland & H. Davenport, "Euclid's algorithm in real quadratic fields," Canad. J. Math., v. 2, 1950, pp. 289-296. MR 0041885 (13:15h)
  • [5] P. M. Cohn, "On the structure of $ {\text{GL}}_2$ of a ring," Publ. Math. IHES, v. 30, 1966, pp. 365-413. MR 0207856 (34:7670)
  • [6] G. E. Cooke, "A weakening of the Euclidean property for integral domains and applications to algebraic number theory I," J. Reine Angew. Math., v. 282, 1976, pp. 133-156. MR 0406973 (53:10758a)
  • [7] G. E. Cooke & P. J. Weinberger, "On the construction of division chains in algebraic number rings, with applications to $ S{L_2}$," Comm. Algebra, v. 3, no. 6, 1975, pp. 481-524. MR 0387251 (52:8094)
  • [8] G. H. Hardy & E. M. Wright, An Introduction to the Theory of Numbers, Oxford Univ. Press, Oxford, 1979. MR 568909 (81i:10002)
  • [9] H. Hasse, Vorlesungen über die Zahlentheorie, Springer-Verlag, Berlin, 1950. MR 0051844 (14:534c)
  • [10] L.-K. Hua, "On the least solution of Pell's equation," Bull. Amer. Math. Soc., v. 48, 1942, pp. 731-735. MR 0007400 (4:130f)
  • [11] A. Hurwitz, Mathematische Werke, 2, Birkhäuser Verlag, Basel, 1963. MR 0154778 (27:4723b)
  • [12] R. Kannan, "Algebraic geometry of numbers," in Annual Review in Computer Science (J. F. Traub, ed.), vol. 2, Annual Reviews Inc., Palo Alto, California, 1987, pp. 231-267. MR 921497 (89a:11131)
  • [13] R. Kannan & A. Bachem, "Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix," SIAM J. Comput., v. 8, 1981, pp. 499-507. MR 573842 (81k:15002)
  • [14] D. E. Knuth, The Art of Computer Programming, vol. 2, Semi-Numerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
  • [15] G. Lamé, "Note sur la limite du nombre des divisions dans la recherche du plus grand diviseur entre deux nombres entiers," C. R. Acad. Sci. Paris, v. 19, 1844, pp. 867-870.
  • [16] S. Lang, Algebraic Number Theory, Addison-Wesley, Reading, Mass., 1970. MR 0282947 (44:181)
  • [17] D. Lazard, "Le meilleur algorithme d'Euclide pour $ K[X]$ et Z," C. R. Acad. Sci. Paris, v. 284, 1977, pp. 1-4. MR 0427214 (55:249)
  • [18] A. K. Lenstra, Jr., H. W. Lenstra & L. Lovász, "Factoring polynomials with rational coefficients," Math. Ann., v. 261, 1982, pp. 515-534. MR 682664 (84a:12002)
  • [19] T. Nagell, "Sur un théorème d'Axel Thue," Ark. Mat., v. 1, no. 33, 1951, pp. 489-496. MR 0049919 (14:247f)
  • [20] M. Pohst & H. Zassenhaus, "An effective number theoretic method of computing the fundamental units of an algebraic number field," Math. Comp., v. 31, 1977, pp. 754-770. MR 0498486 (58:16595)
  • [21] H. Rolletschek, "The Euclidean algorithm for Gaussian integers," Proc. EUROCAL '83, Springer Lecture Notes in Comput. Sci., vol. 162, 1983, pp. 12-23. MR 774800 (86g:11079)
  • [22] H. Rolletschek, "On the number of divisions of the Euclidean algorithm applied to Gaussian integers," J. Symb. Comput., v. 2, 1986, pp. 269-291. MR 860539 (88d:11131)
  • [23] H. Rolletschek, "Shortest division chains in imaginary quadratic number fields," J. Symb. Comput. (To appear.) MR 1056631 (91g:11162)
  • [24] P. Samuel, "About Euclidean rings," J. Algebra, v. 19, 1971, pp. 282-301. MR 0280470 (43:6190)
  • [25] R. J. Schoff, "Quadratic fields and factorization," in Computational Methods in Number Theory, Part II (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Mathematical Centre Tracts, vol. 154, Mathematisch Centrum, Amsterdam, 1982, pp. 89-139. MR 702519 (85g:11118b)
  • [26] R. J. Schoof, "Elliptic curves over finite fields and the computation of square roots $ \bmod p$," Math. Comp., v. 44, 1985, pp. 483-494. MR 777280 (86e:11122)
  • [27] A. Schönhage, "Schnelle Kettenbruchentwicklungen," Acta Inform., v. 1, 1971, pp. 139-144.
  • [28] D. Shanks, Solved and Unsolved Problems in Number Theory I, 2nd ed., Chelsea, New York, 1978. MR 516658 (80e:10003)
  • [29] H. Stark, "A complete determination of complex quadratic fields of class number one," Michigan Math. J., v. 17, 1967, pp. 1-27. MR 0222050 (36:5102)
  • [30] A. Thue, "Et par antydninger til en taltheoretisk methode," Vid. Selsk. Forhandlinger Christiania, no. 7, 1902.
  • [31] P. S. Wang, A p-adic Algorithm for Univariate Partial Fractions, Proc. 1981 ACM Symp. Symbolic Algebraic Comput., 1981, pp. 212-217.
  • [32] P. J. Weinberger, On Euclidean Rings of Algebraic Integers, Proc. Sympos. Pure Math., vol. 24, Amer. Math. Soc., Providence, R.I., 1973, pp. 321-332. MR 0337902 (49:2671)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 11Y40, 11R11, 11R27, 11Y16

Retrieve articles in all journals with MSC: 11Y40, 11R11, 11R27, 11Y16


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1989-0982367-2
Keywords: Quadratic number fields, greatest common divisor, factorization, polynomial-time complexity
Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society