Two Fast Parallel GCD Algorithms of Many Integers
Sidi Mohamed Sedjelmaci · 2017
We present two new parallel algorithms which compute the GCD of n integers of O(n) bits in O(n/log n) time with O(n2+ε) processors in the worst case, for any ε > 0 in CRCW PRAM model. More generally, we prove that computing the GCD of $m$ integers of O(n) bits can be achieved in O(n/log n) parallel time with O(m n1+ε) processors, for any 2 ≤ m ≤ n3/2/log n, i.e. the parallel time does not depend on the number m of integers considered in this range. We suggest an extended GCD version for many integers as well as an algorithm to solve linear Diophantine equations.