Skip to main content
Article
A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM
Information Processing Letters
  • Jonathan P. Sorenson, Butler University
Document Type
Article
Publication Date
1-1-2010
DOI
http://dx.doi.org/10.1016/j.ipl.2009.12.008
Abstract
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 logn/ logn) time using O(n6 + ) processors for any > 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.
Rights

This article was archived with permission from Elsevier, all rights reserved.

Citation Information
Jonathan P. Sorenson. "A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM" Information Processing Letters Vol. 110 Iss. 5 (2010) p. 198 - 201
Available at: http://works.bepress.com/jonathan_sorenson/2/