The accelerated integer GCD algorithm

DOI10.1145/200979.201042MaRDI QIDQ4371587zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Kenneth Weber

Publication date 26 January 1998

Published in ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL http://www.acm.org/pubs/contents/journals/toms/1995-21/

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

• A modular integer GCD algorithm
• Improvements on the accelerated integer GCD algorithm
• Two Fast GCD Algorithms
• Parallel implementation of the accelerated integer GCD algorithm

Cited in

(21)

• Generating the greatest common divisor, and limitations of primitive recursive algorithms
• A modular reduction for GCD computation.
• Worst-case analysis of Weber's GCD algorithm
• Polynomial greatest common divisor as a solution of system of linear equations
• An effective programming of GCD algorithms for natural numbers
• An approximating k-ary GCD algorithm
• GCD calculation in the search task of pseudoprime and strong pseudoprime numbers
• Parallel implementation of the accelerated integer GCD algorithm
• Improvements on the accelerated integer GCD algorithm
• scientific article; zbMATH DE number 3908170 (Why is no real title available?)
• Fast computation of GCDs
• Two Fast GCD Algorithms
• scientific article; zbMATH DE number 1736309 (Why is no real title available?)
• A modular integer GCD algorithm
• An extended Jebelean-Weber-Sedjelmaci GCD algorithm
• On Schönhage's algorithm and subquadratic integer gcd computation
• A Paper-and-Pencil gcd Algorithm for Gaussian Integers
• Automata, Languages and Programming
• \((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
• Calculation of Bezout coefficients for a k-ary GCD algorithm

Describes a project that uses

Uses Software

• gmp

This page was built for publication: The accelerated integer GCD algorithm

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