Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Computing greatest common divisors and factorizations in quadratic number fields
HTML articles powered by AMS MathViewer

by Erich Kaltofen and Heinrich Rolletschek PDF
Math. Comp. 53 (1989), 697-720 Request permission

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
Similar Articles
Additional Information
  • © Copyright 1989 American Mathematical Society
  • 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