A randomized sublinear time parallel GCD algorithm for the EREW PRAM

DOI10.1016/J.IPL.2009.12.008zbMath1209.68627OpenAlexW2158251041MaRDI QIDQ991752

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

greatest common divisorparallel algorithmssmooth numbersrandomized algorithmsnumber theoretic algorithmsalgorithm analysis

Mathematics Subject Classification ID

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

Cites Work

• An improved parallel algorithm for integer GCD
• Fast arithmetics using Chinese remaindering
• A parallel extended GCD algorithm
• Efficient algorithms for computing the Jacobi symbol
• Integers without large prime factors
• Two fast parallel prime number sieves
• A modular reduction for GCD computation.
• Fast multiplication of large numbers
• On a parallel Lehmer-Euclid GCD algorithm
• Modular exponentiation via the explicit Chinese remainder theorem
• Log Depth Circuits for Division and Related Problems
• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
• Two Fast GCD Algorithms
• Fast parallel matrix and GCD computations
• Algorithmic Number Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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