Two Fast GCD Algorithms

DOI10.1006/JAGM.1994.1006zbMath0815.11065DBLPjournals/jal/Sorenson94OpenAlexW2073952448WikidataQ29542672 ScholiaQ29542672MaRDI QIDQ4289843

Jonathan P. Sorenson

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

zbMATH Keywords

greatest common divisorPascalEuclidean algorithm\(k\)-ary GCD algorithmGCD algorithms\(k\)-ary shift algorithmsCRCW PRAM implementation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05)

Related Items (18)

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 ⋮ On the continued fraction with rational partial quotients ⋮ Cryptanalysis of algebraic verifiable delay functions ⋮ 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