A randomized sublinear time parallel GCD algorithm for the EREW PRAM
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 log log n/log n) time using O (n(6+epsilon)) processors for any epsilon > 0 on the EREW PRAM parallel model of computation. The algorithm either gives a correct answer or reports failure. We believe this to be the first randomized sublinear time algorithm on the EREW PRAM for this problem. (C) 2009 Elsevier B.V. All rights reserved.
parallel algorithms greatest common divisor randomized algorithms algorithm analysis number theoretic algorithms smooth numbers