Two Fast GCD Algorithms
From MaRDI portal
Publication:4289843
DOI10.1006/jagm.1994.1006zbMath0815.11065OpenAlexW2073952448WikidataQ29542672 ScholiaQ29542672MaRDI QIDQ4289843
Publication date: 9 July 1995
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1994.1006
greatest common divisorPascalEuclidean algorithm\(k\)-ary GCD algorithmGCD algorithms\(k\)-ary shift algorithmsCRCW PRAM implementation
Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)
Related Items (16)
An approximating \(k\)-ary GCD algorithm ⋮ Improvements on the accelerated integer GCD algorithm ⋮ Jebelean-Weber's algorithm without spurious factors ⋮ On analogues of Heilbronn's theorem ⋮ An extended Jebelean^ WeberNSedjelmaci GCD algorithm ⋮ A modular reduction for GCD computation. ⋮ An effective programming of GCD algorithms for natural numbers ⋮ A space-efficient fast prime number sieve ⋮ Calculation of Bezout coefficients for a \(k\)-ary GCD algorithm ⋮ \((1+i)\)-ary GCD computation in \(\mathbb Z[i\) as an analogue to the binary GCD algorithm.] ⋮ On Schönhage's algorithm and subquadratic integer 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 ⋮ Worst-case analysis of Weber's GCD algorithm
This page was built for publication: Two Fast GCD Algorithms
