Fast computation of GCDs

1 January 1973

proceedings article
Published by Association for Computing Machinery (ACM)

p. 142-151
https://doi.org/10.1145/800125.804045

Abstract

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 loga N), then their GCD can be computed in O(N loga+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.

Keywords

This publication has 0 references indexed in Scilit: