A new algorithm and refined bounds for extended gcd computation

DOI10.1007/3-540-61581-4_50MaRDI QIDQ4375607zbMATH OpenFDO

Authors David J. Ford, George Havas

Publication date 15 November 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61581-4_50

zbMATH Keywords

algorithmboundsextended gcd computation

Mathematics Subject Classification ID

Multiplicative structure; Euclidean algorithm; greatest common divisors (11A05) Number-theoretic algorithms; complexity (11Y16)

Review text

Let \(a_1,\dots, a_n\) be given integers with \(\text{gcd }g\). It is required to find integers \(x_1,\dots, x_n\) such that \(\sum_{i=1}^n a_ix_i= g\). The authors propose a method that consists of the construction of a matrix \(P\), the first row of which is \(x_1,\dots, x_n\). No run times, that would enable comparisons to be made with other methods, are given. Optimal bounds are obtained for the \(x_1\). The method given on p. 147 for the construction of \(P\) seems to require the answer to be known beforehand: a worked example would have clarified what the authors intended. For the entire collection see [Zbl 0852.00023].

Recommendations

• scientific article; zbMATH DE number 1254257
• scientific article; zbMATH DE number 1156678
• scientific article; zbMATH DE number 1253972
• A systolic algorithm for extended GCD computation

Cited in

(5)

• scientific article; zbMATH DE number 1736309 (Why is no real title available?)
• scientific article; zbMATH DE number 1156678 (Why is no real title available?)
• Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction (addenda and errata)
• ON THE CONSTRUCTION OF A PSE FOR GCD COMPUTATION
• scientific article; zbMATH DE number 3995051 (Why is no real title available?)

This page was built for publication: A new algorithm and refined bounds for extended gcd computation

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