A modular integer GCD algorithm

DOI10.1016/J.JALGOR.2004.06.006MaRDI QIDQ4652409zbMATH OpenOpenAlexFDO

Authors Kenneth Weber, Vilmar Trevisan, Luiz Felipe Martins

Publication date 22 February 2005

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://engagedscholarship.csuohio.edu/scimath_facpub/156

zbMATH Keywords

Integer GCDModular representationParallel algorithmResidue arithmetic

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Parallel algorithms in computer science (68W10) Symbolic computation and algebraic computation (68W30)

Recommendations

• An improved parallel algorithm for integer GCD
• Two Fast GCD Algorithms
• Parallel implementation of the accelerated integer GCD algorithm
• The accelerated integer GCD algorithm
• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers

Cited in

(23)

• A parallel extended GCD algorithm
• A systolic algorithm for extended GCD computation
• The iterated mod problem
• A modular reduction for GCD computation.
• A double-digit Lehmer-Euclid algorithm for finding the GCD of long integers
• An effective programming of GCD algorithms for natural numbers
• Some related functions to integer GCD and coprimality
• scientific article; zbMATH DE number 4152522 (Why is no real title available?)
• scientific article; zbMATH DE number 3961705 (Why is no real title available?)
• Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers
• scientific article; zbMATH DE number 1263309 (Why is no real title available?)
• Two Fast GCD Algorithms
• A lower bound for integer greatest common divisor computations
• The accelerated integer GCD algorithm
• scientific article; zbMATH DE number 1461539 (Why is no real title available?)
• scientific article; zbMATH DE number 841617 (Why is no real title available?)
• Gcd Modulo a Primary Triangular Set of Dimension Zero
• Two fast parallel GCD algorithms of many integers
• A Paper-and-Pencil gcd Algorithm for Gaussian Integers
• scientific article; zbMATH DE number 3341178 (Why is no real title available?)
• An improved parallel algorithm for integer GCD
• The area-time complexity of the greatest common divisor problem: A lower bound
• A randomized sublinear time parallel GCD algorithm for the EREW PRAM

This page was built for publication: A modular integer GCD algorithm

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