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
Voir la notice du chapitre de livre provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
volume = {161},
number = {1},
year = {2019},
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 PB - mathdoc 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 %I mathdoc %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/