ACS/IEEE International Conference on Computer Systems and Applications (AICCSA'01)
On a Parallel Extended Euclidean Algorithm
Beirut, Lebanon
June 25-June 29
ISBN: 0-7695-1165-1
Abstract: A new parallelization of the Extended Euclidean GCD algorithm is proposed. It matches the best existing integer GCD algorithms since it can be achieved in parallel Oeps(n/log n) using only n1+eps processors on a Priority CRCW PRAM, for any constant eps > 0.