×

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: DOI