A randomized sublinear time parallel GCD algorithm for the EREW PRAM

DOI10.1016/J.IPL.2009.12.008MaRDI QIDQ991752zbMATH OpenOpenAlexFDO

Authors Jonathan P. Sorenson

Publication date 7 September 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://digitalcommons.butler.edu/facsch_papers/81

zbMATH Keywords

randomized algorithmsnumber theoretic algorithmsparallel algorithmsalgorithm analysisgreatest common divisorsmooth numbers

Mathematics Subject Classification ID

Randomized algorithms (68W20) Parallel algorithms in computer science (68W10)

Recommendations

• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
• An improved parallel algorithm for integer GCD
• A modular integer GCD algorithm
• Two fast parallel GCD algorithms of many integers
• On a parallel Lehmer-Euclid GCD algorithm

Cites work

• scientific article; zbMATH DE number 989379 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 2154292 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• A modular reduction for GCD computation.
• A parallel extended GCD algorithm
• Algorithmic Number Theory
• An improved parallel algorithm for integer GCD
• Efficient algorithms for computing the Jacobi symbol
• Fast arithmetics using Chinese remaindering
• Fast multiplication of large numbers
• Fast parallel matrix and GCD computations
• Integers without large prime factors
• Log Depth Circuits for Division and Related Problems
• Modular exponentiation via the explicit Chinese remainder theorem
• On a parallel Lehmer-Euclid GCD algorithm
• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
• Two Fast GCD Algorithms
• Two fast parallel prime number sieves

Cited in

(1)

• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers

This page was built for publication: A randomized sublinear time parallel GCD algorithm for the EREW PRAM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991752)