2 FAST GCD ALGORITHMS

We present two new algorithms for computing greatest common divisors: the right- and left-shift k-ary GCD algorithms. These algorithms are generalizations of the binary and left-shift binary algorithms. Interestingly, both new algorithms have sequential versions that are practical and efficient and parallel versions that rival the best previous parallel GCD algorithms. We show that sequential versions of both algorithms take Θ(n2/log n) bit operations in the worst case to compute the GCD of two n-bit integers. This compares favorably to the Euclidean and both binary algorithms, which take Θ(n2) time. In practice, we implemented multiple-precision versions of these GCD algorithms, and we found that both k-ary algorithms are faster than the Euclidean and binary algorithms on inputs of 100 to 1000 decimal digits in length. We show that parallel versions of both algorithms match the complexity of the best previous parallel GCD algorithm due to Chor and Goldreich. Specifically, if log n ≤ k ≤ 2n and k is a power of two, then both algorithms run in O(n/log k + log2n log log n) time using a number of processors bounded by a polynomial in n and k on a common CRCW PRAM. We also discuss extended versions of both algorithms. © 1994 Academic Press, Inc.