zbMATH — the first resource for mathematics

Fast computation of GCDs. (English) Zbl 0306.68027
STOC ’73, Proc. 5th ann. ACM Symp. Theor. Comput., Austin 1973, 142-151 (1973).
Summary: An integer greatest common divisor (GCD) algorithm due to Schönhage is generalized to hold in all Euclidean domains which possess a fast multiplication algorithm. It is shown that if two $$N$$ precision elements can be multiplied in $$O(N \log^a N)$$, then their GCD can be computed in $$O(N \log^{a+1} N)$$. As a consequence, a new faster algorithm for multivariate polynomial GCD’s can be derived and with that new bounds for rational function manipulation.

MSC:
 68Q25 Analysis of algorithms and problem complexity 68W30 Symbolic computation and algebraic computation 11Y16 Number-theoretic algorithms; complexity
Full Text: