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.


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


Zbl 0303.00008
Full Text: DOI