Geodesic
Calculation of Bezout's coefficients for $k$-ary algorithm of greatest common divisor
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2017), pp. 30-38

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{IVM_2017_11_a3,
     author = {Sh. T. Ishmukhametov and B. G. Mubarakov and Kamal Maad Al-Anni},
     title = {Calculation of {Bezout's} coefficients for $k$-ary algorithm of greatest common divisor},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {30--38},
     publisher = {mathdoc},
     number = {11},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2017_11_a3/}
}
TY  - JOUR
AU  - Sh. T. Ishmukhametov
AU  - B. G. Mubarakov
AU  - Kamal Maad Al-Anni
TI  - Calculation of Bezout's coefficients for $k$-ary algorithm of greatest common divisor
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2017
SP  - 30
EP  - 38
IS  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2017_11_a3/
LA  - ru
ID  - IVM_2017_11_a3
ER  - 
%0 Journal Article
%A Sh. T. Ishmukhametov
%A B. G. Mubarakov
%A Kamal Maad Al-Anni
%T Calculation of Bezout's coefficients for $k$-ary algorithm of greatest common divisor
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2017
%P 30-38
%N 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2017_11_a3/
%G ru
%F IVM_2017_11_a3
Sh. T. Ishmukhametov; B. G. Mubarakov; Kamal Maad Al-Anni. Calculation of Bezout's coefficients for $k$-ary algorithm of greatest common divisor. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 11 (2017), pp. 30-38. http://geodesic.mathdoc.fr/item/IVM_2017_11_a3/