%0 Journal Article
%T A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM
%A Jonathan P. Sorenson
%J Computer Science
%D 2009
%I arXiv
%R 10.1016/j.ipl.2009.12.008
%X We present a randomized parallel algorithm that computes the greatest common divisor of two integers of n bits in length with probability 1-o(1) that takes O(n loglog n / log n) expected time using n^{6+\epsilon} processors on the EREW PRAM parallel model of computation. We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem.
%U http://arxiv.org/abs/0907.0718v2