Moenck, R. T. 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. Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page Cited in 1 ReviewCited in 20 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68W30 Symbolic computation and algebraic computation 11Y16 Number-theoretic algorithms; complexity PDF BibTeX Full Text: DOI