Calculation of extended gcd by normalization
DOI: 440 Downloads 6599 Views
Author(s)
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 |