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/

[1] Krendell R., Pomerans K., Prostye chisla: kriptograficheskie i vychislitelnye aspekty, URRS, M., 2011

[2] Sorenson J., The $k$-ary GCD algorithm, Techn. Report, University of Wisconsin-Madison, 1990, 20 pp.

[3] Sorenson J., “Two fast GCD algorithms”, J. Algorithms, 16:1 (1994), 110–144 | DOI | MR | Zbl

[4] Weber K., “The accelerated integer GCD algorithm”, ACM Trans. Math. Software, 21:1 (1995), 1–12 | DOI | MR

[5] Jebelean T., “A generalization of the binary GCD algorithm”, Proc. of Intern. Symp. on Symb. and Algebr. Comp., ISSAC'93, 1993, 111–116 | Zbl

[6] Ishmukhametov S. T., Rubtsova R. G., “A fast algorithm for counting GCD of natural numbers”, Proc. Intern. conf. Algebra, Analysis and Geometry, KFU, Kazan, 2016, 52–53

[7] Ishmukhametov S. T., “An approximating $k$-ary GCD algorithm”, Lobachevskii J. Math., 37:6 (2016), 722–728 | DOI | MR

[8] Hardy G. H., Wright E. M., An introduction to the theory of numbers, 4th Ed., Clarendon Press, Oxford, 1959 | MR

[9] Grekhem R., Knut D., Patashnik O., Konkretnaya matematika. Matematicheskie osnovy informatiki, 2-e ispr. izd., Vilyams, 2015

[10] Ishmukhametov Sh. T., Metody faktorizatsii, KFU, Kazan, 2011

[11] Ishmukhametov Sh. T., Rubtsova R. G., Matematicheskie metody zaschity informatsii, Elektronnoe uchebnoe posobie, , KFU, Kazan, 2012 http://kpfu.ru/docs/F366166681/mzi.pdf

[12] Wang X., Pan V., “Acceleration of Euclidian algorithm and rational nimber reconstruction”, Siam J. Comp., 32:2 (2003), 548–556 | DOI | MR | Zbl