Two Fast GCD Algorithms

DOI10.1006/JAGM.1994.1006MaRDI QIDQ4289843zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

\(k\)-ary GCD algorithm\(k\)-ary shift algorithmsCRCW PRAM implementationEuclidean algorithmGCD algorithmsgreatest common divisorPascal

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1254258
• Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x]$
• The accelerated integer GCD algorithm
• A modular integer GCD algorithm
• An improved parallel algorithm for integer GCD
• Algorithmic Number Theory
• The mixed binary Euclid algorithm
• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
• New binary Euclidean algorithms
• scientific article; zbMATH DE number 841617

Cited in

(33)

• A parallel extended GCD algorithm
• Analysis of a left-shift binary GCD algorithm
• On primitive recursive algorithms and the greatest common divisor function
• A modular reduction for GCD computation.
• Worst-case analysis of Weber's GCD algorithm
• A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers
• On analogues of Heilbronn's theorem
• An effective programming of GCD algorithms for natural numbers
• A novel fast hybrid GCD computation algorithm
• An approximating k-ary GCD algorithm
• Extending the binary gcd algorithms
• The mixed binary Euclid algorithm
• Some related functions to integer GCD and coprimality
• Improvements on the accelerated integer GCD algorithm
• Precise Analyses of the Right- and Left-Shift Greatest Common Divisor Algorithms for $GF(q)[x]$
• Fast computation of GCDs
• scientific article; zbMATH DE number 1254258 (Why is no real title available?)
• scientific article; zbMATH DE number 1263309 (Why is no real title available?)
• scientific article; zbMATH DE number 1736309 (Why is no real title available?)
• The accelerated integer GCD algorithm
• A modular integer GCD algorithm
• scientific article; zbMATH DE number 799776 (Why is no real title available?)
• scientific article; zbMATH DE number 841617 (Why is no real title available?)
• An extended Jebelean-Weber-Sedjelmaci GCD algorithm
• On Schönhage's algorithm and subquadratic integer gcd computation
• Algorithmic Number Theory
• \((1+i)\)-ary GCD computation in \(\mathbb Z[i]\) as an analogue to the binary GCD algorithm.
• On the continued fraction with rational partial quotients
• Cryptanalysis of algebraic verifiable delay functions
• A space-efficient fast prime number sieve
• Calculation of Bezout coefficients for a k-ary GCD algorithm
• Jebelean-Weber's algorithm without spurious factors
• A randomized sublinear time parallel GCD algorithm for the EREW PRAM

This page was built for publication: Two Fast GCD Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4289843)