An improved parallel algorithm for integer GCD

DOI10.1007/BF01840374zbMath0689.68046WikidataQ56048613 ScholiaQ56048613MaRDI QIDQ582082

Benny Chor, Oded Goldreich

Publication date: 1990

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmCRCW model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Related Items (6)

Complexity of computation in finite fields ⋮ A modular reduction for GCD computation. ⋮ A randomized sublinear time parallel GCD algorithm for the EREW PRAM ⋮ A parallel extended GCD algorithm ⋮ The Mixed Binary Euclid Algorithm ⋮ Some Related Functions to Integer GCD and Coprimality

Cites Work

• Unnamed Item
• Unnamed Item
• Unbounded fan-in circuits and associative functions
• Parallel computation and conflicts in memory access
• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
• A universal interconnection pattern for parallel computers
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Cellular automata complexity trade-offs
• Majority Gate Networks

This page was built for publication: An improved parallel algorithm for integer GCD