A parallel extended GCD algorithm
type: Item
instance of: scholarly article
title: A parallel extended GCD algorithm
zbMATH Open document ID: 1193.11118
author: Sidi Mohamed Sedjelmaci
published in: Journal of Discrete Algorithms
publication date: 2009-05-13T00:00:00Z
review text: This paper describes two new parallel algorithms for computing the greatest common divisor (GCD) of two integers \(u\) and \(v\). The second algorithm solves the extended GCD problem in that it also returns the Bézout coefficients, integers \(a\) and \(b\) such that \(|a| \leq v/2d\) and \(|b| \leq u/2d\) and \(au + bv = \gcd(u,v).\) The complexity of both algorithms matches the best-known result for these problems, namely time complexity \(O_\varepsilon(n / \log n)\) using \(n^{1 + \varepsilon}\) processors, where \(n\) is the bit-length of the larger of \(u\) and \(v\). The main result in both algorithms is a novel reduction algorithm that finds integers \(a\) and \(b\) such that \(|au - bv| < 2v/k\) for \(k = O(n)\) using the \(O(\log n)\) most significant bits of \(u\) and \(v\).
reviewed by: Michael J. Jacobson jun.
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11A05
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5553605
zbMATH Keywords: integer greatest common divisor (GCD)
zbMATH Keywords: parallel GCD algorithm
zbMATH Keywords: extended GCD algorithm
zbMATH Keywords: complexity analysis
zbMATH Keywords: number theory
MaRDI profile type: Publication
full work available at URL: j.jda.2006.12.009
OpenAlex ID: W2040055854
cites work: An improved parallel algorithm for integer GCD
cites work: Modern computer algebra
cites work: Q3856819
cites work: Q4234183
cites work: Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
cites work: Q4385522
cites work: Q4349924
cites work: On a parallel Lehmer-Euclid GCD algorithm
cites work: Two Fast GCD Algorithms
cites work: Q4227305
cites work: Parallel implementation of the accelerated integer GCD algorithm
DOI: 10.1016/J.JDA.2006.12.009
description: scientific article; zbMATH DE number 5553605