|
Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 2017, Number 11, Pages 30–38
(Mi ivm9298)
|
|
|
|
This article is cited in 8 scientific papers (total in 8 papers)
Calculation of Bezout's coefficients for $k$-ary algorithm of greatest common divisor
Sh. T. Ishmukhametova, B. G. Mubarakova, Kamal Maad Al-Annib a Kazan Federal University,
18 Kremlyovskaya str., Kazan, 420008 Russia
b University of Strasbourg,
4 Rue Blaise Pascal, Strasbourg, 67081 France
Abstract:
Bezout's equation is a representation of the greatest common divisor $d$ of two integers $A$ and $B$ as a linear combination $Ax+By=d$, where $x$ and $y$ are integers called Bezout's coefficients. Usually Bezout's coefficients are caclulated using the extended version of the classical Euclidian algorithm.
We elaborate a new algorithm for calculating Bezout's coefficients based on the $k$-ary GCD algorithm. This problem has numerous applications in the number theory and cryptography, for example, for calculation of multiplicative inverse elements in modular arithmetic.
Keywords:
Euclidian algorithm, extended Euclidian algorithm, $k$-ary GCD algorithm, calculation of inverse elements by module.
Received: 24.06.2016
Citation:
Sh. T. Ishmukhametov, B. G. Mubarakov, Kamal Maad Al-Anni, “Calculation of Bezout's coefficients for $k$-ary algorithm of greatest common divisor”, Izv. Vyssh. Uchebn. Zaved. Mat., 2017, no. 11, 30–38; Russian Math. (Iz. VUZ), 61:11 (2017), 26–33
Linking options:
https://www.mathnet.ru/eng/ivm9298 https://www.mathnet.ru/eng/ivm/y2017/i11/p30
|
Statistics & downloads: |
Abstract page: | 541 | Full-text PDF : | 179 | References: | 45 | First page: | 11 |
|