Calculation of extended gcd by normalization

Volume 3, Issue 3, June 2018     |     PP. 118-131      |     PDF (269 K)    |     Pub. Date: August 2, 2018
DOI:    440 Downloads     7806 Views  

Author(s)

WOLF Marc, Independent researchers.
WOLF François, Independent researchers.
LE COZ Corentin, Independent researchers.

Abstract
We propose a new algorithm solving the extended gcd problem, which provides a solution minimizing one of the two coordinates. The algorithm relies on elementary arithmetic properties.

Keywords
extended gcd; normalizer; co-normalizer; minimizing one of the two coordinates; normal solution; linear diophantine equation; mixed Euclid algorithm

Cite this paper
WOLF Marc, WOLF François, LE COZ Corentin, Calculation of extended gcd by normalization , SCIREA Journal of Mathematics. Volume 3, Issue 3, June 2018 | PP. 118-131.

References

[ 1 ] R. P. Brent, H. T. Kung, Systolic VLSI arrays for polynomial GCD computations. IEEE Trans. Comput. C-33, 731-736 (1984)
[ 2 ] R. P. Brent. An improved Monte Carlo factorization algorithm. BIT 20, 176-184 (1980).
[ 3 ] Denis Serre. Matrices, theory and Applications. Springer 2010.
[ 4 ] Doran, Lu, Smith. New algorithms for modular inversion and representation by binary quadrtic forms arising from structure in the Euclidean algorithm, 2015. arXiv:1408.4638v2
[ 5 ] H. Leung, A Note on Extended Euclid’s Algorithm, arXiv:1607.00106, 2016
[ 6 ] R. P. Brent. Further analysis of the Binary Euclidean algorithm. PRG TR-7-99. 1999