A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM

Jonathan P. Sorenson

doi:10.1016/j.ipl.2009.12.008

A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM

Research output: Contribution to journal › Article › peer-review

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.

Original language	American English
Journal	Scholarship and Professional Work - LAS
Volume	110
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2009.12.008
State	Published - Jan 1 2010

Keywords

EREW PRAM
algorithm analysis
algorithms
greatest common divisor
smooth numbers

Disciplines

Computer Sciences
Theory and Algorithms

Access to Document

10.1016/j.ipl.2009.12.008License: Unspecified

A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PFinal published version, 473 KBLicense: Unspecified

Cite this

@article{129bce4183ff4713b63bba7982581aca,

title = "A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM",

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.",

keywords = "EREW PRAM, algorithm analysis, algorithms, greatest common divisor, smooth numbers",

author = "Sorenson, {Jonathan P.}",

year = "2010",

month = jan,

day = "1",

doi = "10.1016/j.ipl.2009.12.008",

language = "American English",

volume = "110",

journal = "Scholarship and Professional Work - LAS",

number = "5",

}

TY - JOUR

T1 - A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM

AU - Sorenson, Jonathan P.

PY - 2010/1/1

Y1 - 2010/1/1

N2 - 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.

AB - 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.

KW - EREW PRAM

KW - algorithm analysis

KW - algorithms

KW - greatest common divisor

KW - smooth numbers

UR - https://digitalcommons.butler.edu/facsch_papers/81

U2 - 10.1016/j.ipl.2009.12.008

DO - 10.1016/j.ipl.2009.12.008

M3 - Article

VL - 110

JO - Scholarship and Professional Work - LAS

JF - Scholarship and Professional Work - LAS

IS - 5

ER -

A Randomized Sublinear Time Parallel GCD Algorithm for the EREW PRAM

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this