A randomized sublinear time parallel GCD algorithm for the EREW PRAM

作者：Sorenson Jonathan P^*

来源：Information Processing Letters, 2010, 110(5): 198-201.

DOI：10.1016/j.ipl.2009.12.008

• Parallel algorithms
• Randomized algorithms
• Algorithm analysis
• Greatest common divisor
• Number theoretic algorithms
• Smooth numbers

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.

• 出版日期2010-2-1