Geodesic
On acceleration of the $k$-ary GCD algorithm
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 1, pp. 110-118 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this paper, methods of acceleration of GCD algorithms for natural numbers based on the $k$-ary GCD algorithm have been studied. The $k$-ary algorithm was elaborated by J. Sorenson in 1990. Its main idea is to find for given numbers $A$, $B$ and a parameter $k$, co-prime to both $A$ and $B$, integers $x$ and $y$ satisfying the equation $Ax+By\equiv 0 \bmod k.$ Then, integer $C=(Ax+By)/k$ takes a value less than $A$. At the next iteration, a new pair $(B, C)$ is formed. The $k$-ary GCD algorithm ensures a significant diminishing of the number of iterations against the classical Euclidian scheme, but the common productivity of the $k$-ary algorithm is less than the Euclidian method. We have suggested a method of acceleration for the $k$-ary algorithm based on application of preliminary calculated tables of parameters like as inverse by module $k$. We have shown that the $k$-ary GCD algorithm overcomes the classical Euclidian algorithm at a sufficiently large $k$ when such tables are used.
Keywords: greatest common divisor for natural numbers, Euclidian GCD algorithm, binary GCD algorithm, $k$-ary GCD algorithm. 
@article{UZKU_2019_161_1_a7,
     author = {I. Amer and S. T. Ishmukhametov},
     title = {On acceleration of the $k$-ary {GCD} algorithm},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {110--118},
     year = {2019},
     volume = {161},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a7/}
}
TY  - JOUR
AU  - I. Amer
AU  - S. T. Ishmukhametov
TI  - On acceleration of the $k$-ary GCD algorithm
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2019
SP  - 110
EP  - 118
VL  - 161
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a7/
LA  - ru
ID  - UZKU_2019_161_1_a7
ER  - 
%0 Journal Article
%A I. Amer
%A S. T. Ishmukhametov
%T On acceleration of the $k$-ary GCD algorithm
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2019
%P 110-118
%V 161
%N 1
%U http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a7/
%G ru
%F UZKU_2019_161_1_a7
I. Amer; S. T. Ishmukhametov. On acceleration of the $k$-ary GCD algorithm. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 161 (2019) no. 1, pp. 110-118. http://geodesic.mathdoc.fr/item/UZKU_2019_161_1_a7/

[1] Ishmukhametov Sh.T., Methods of Factorization of Positive Integers, Izd. Kazan. Univ., Kazan, 2011, 189 pp. (In Russian)

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

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

[4] Knuth D., The Art of Computer Programming: Seminumerical Algorithms, v. 2, Addison-Wesley, 1997, xiv+762 pp. | MR

[5] Ishmukhametov S. T., Rubtsova R. G., “A parallel computation of the GCD of natural numbers”, Parallel Computational Technologies, XI Int. Conf., PCT' 2017 (Kazan, 2017), 2017, 120–129 (In Russian)

[6] Sorenson J., The $k$-ary GCD Algorithm, Computer Sciences Technical Report CS-TR-90-979, Univ. of Wisconsin, Madison, 1990, 20 pp.

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

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

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

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

[11] Maximov K. L., Ishmukhametov S. T., “About algorithm of smooth numbers calculation”, Res. J. Appl. Sci., 10:8 (2015), 376–380

[12] Ishmukhametov S. T., Mubarakov B. G., “On practical aspects of the Miller–Rabin Primality Test”, Lobachevskii J. Math., 34:4 (2013), 304–312 | DOI | MR | Zbl