Parallel Implementation of the Accelerated Integer GCD Algorithm

The accelerated integer greatest common divisor (GCD) algorithm has been shown to be one of the most efficient in practice. This paper describes a parallel implementation of the accelerated algorithm for the Sequent Balance, a shared-memory multiprocessor. For input of roughly 10 000 digits, it displays speed-ups of 1.6, 2.5, 3.4 and 4.0 using 2, 4, 8 and 16 processors, respectively.