Extending the binary gcd algorithms

MaRDI QIDQ2764238zbMATH OpenFDO

Authors Przemysław Kubiak

Publication date 4 July 2002

zbMATH Keywords

extended binary gcd algorithm

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to number theory (11-04) Number-theoretic algorithms; complexity (11Y16)

Review text

The extended binary gcd algorithm, that finds \(u,v\), and \((A,B)\) for given \(A\) and \(B\) such that \(uA+ vB= (A,B)\), is speeded up by arranging for shifts as large as possible to be used at each stage. Various algorithms are given in detail and results of experiments, on 40000 pairs \(A,B\) for each of 24 different lengths of numbers up to 1030 bits, are reported. The results indicate that execution time is roughly halved.NEWLINENEWLINEFor the entire collection see [Zbl 0976.00054].

Recommendations

• scientific article; zbMATH DE number 3995051
• Analysis of a left-shift binary GCD algorithm
• The mixed binary Euclid algorithm
• Algorithmic Number Theory
• Two Fast GCD Algorithms

Cited in

(4)

• Analysis of a left-shift binary GCD algorithm
• scientific article; zbMATH DE number 1156678 (Why is no real title available?)
• scientific article; zbMATH DE number 2154292 (Why is no real title available?)
• scientific article; zbMATH DE number 3995051 (Why is no real title available?)

This page was built for publication: Extending the binary gcd algorithms

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