Geodesic
Efficient removal of divisors in the $k$-ary algorithm
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 3, pp. 393-404 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The $k$-ary algorithm is one of the most efficient methods for finding the greatest common divisor (GCD). To find GCD of $u$ and $v$, we performed the $k$-ary reduction $t = |a u + b v|/k$, where $ 0 < a,$ $ |b| \leq \lceil \sqrt{k} \rceil{:}$ $ a u + b v \equiv{} 0 \pmod k$. The reduction step is used when $u$ and $v$ have almost the same size. Otherwise, we appled the dmod operation $|u-cv|/2^L$, where $c = u v^{-1} \bmod 2^L$, $L = L(u) - L(v)$, $L(a)$ is a function returning the binary length of $a$. We considered that $k$-ary algorithm works with multi-precision integers and $k=2^{2W}$, where $W$ is the word size. We accelerated this method by minimizing the number of divisors removal operations. We combined this procedure with a division operation by $2^{i W}$ and described its fast implementation. We proposed a new way to compute coefficients that allows to get rid of divisors removal before the reduction step and to produce that operation before dmod operation in $1/3$ of the cases. The proposed method accelerates the main loop of the $k$-ary algorithm by $3$–$16\%$. The results obtained are important in many algorithms in cryptography.
Keywords: greatest common divisor, $k$-ary algorithm, factors removal, multi-precision integers. 
@article{UZKU_2019_161_3_a5,
     author = {R. R. Enikeev},
     title = {Efficient removal of divisors in the $k$-ary algorithm},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {393--404},
     year = {2019},
     volume = {161},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2019_161_3_a5/}
}
TY  - JOUR
AU  - R. R. Enikeev
TI  - Efficient removal of divisors in the $k$-ary algorithm
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2019
SP  - 393
EP  - 404
VL  - 161
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2019_161_3_a5/
LA  - ru
ID  - UZKU_2019_161_3_a5
ER  - 
%0 Journal Article
%A R. R. Enikeev
%T Efficient removal of divisors in the $k$-ary algorithm
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2019
%P 393-404
%V 161
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2019_161_3_a5/
%G ru
%F UZKU_2019_161_3_a5
R. R. Enikeev. Efficient removal of divisors in the $k$-ary algorithm. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 3, pp. 393-404. http://geodesic.mathdoc.fr/item/UZKU_2019_161_3_a5/

[1] B. Gladman, W. Hart, J. Moxham et al., MPIR: Multiple Precision Integers and Rationals, Version 2.7.0, , 2015 http://mpir.org

[2] T. Jebelean, “A double-digit Lehmer–Euclid algorithm for finding the GCD of long integers”, J. Symbol. Computation, 19:1–3 (1995), 145–157 | DOI | MR | Zbl

[3] J. Stein, “Computational problems associated with Racah algebra”, J. Comput. Phys., 1:3 (1967), 397–405 | DOI | Zbl

[4] D. E. Knuth, The Art of Computer Programming, v. 2, Seminumerical algorithms, Vil'yams, M., 2001, 832 pp. (In Russian)

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

[6] K. Weber, “The accelerated integer GCD algorithm”, ACM Transact. Math. Software, 21:1 (1995), 111–122 | DOI | MR | Zbl

[7] T. Jebelean, “A generalization of the binary GCD algorithm”, Proc. 1993 Int. Symp. on Symbolic and Algebraic Computation, ACM, N. Y., 1993, 111–116 | DOI | Zbl

[8] V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge Univ. Press, Cambridge, 2008, 598 pp. | MR

[9] T. Jebelean, “An algorithm for exact division”, J. Symbol. Comput., 15:2 (1993), 169–180 | DOI | MR | Zbl

[10] Sh. T. Ishmukhametov, B. G. Mubarakov, “Kamal Al-Anni Maad Calculation of Bezout's coefficients for the $k$-ary algorithm of finding GCD”, Russ. Math., 61:11 (2017), 26–33 | DOI | MR | Zbl

[11] R. R. Enikeev, “Computing Bezout coefficients using extended generalized binary algorithm”, Information Technology and Mathematical Modeling (ITMM-2017), Proc. XVI Int. Conf. Dedicated to A.F. Terpugov, Izd. Nauchn.-Tekh. Lit., Tomsk, 2017, 284–291 (In Russian)