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
MathSciNet review: 982367
Full-text PDF Free Access

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

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

Keywords: Quadratic number fields, greatest common divisor, factorization, polynomial-time complexity
Article copyright: © Copyright 1989 American Mathematical Society