On acceleration of the $k$-ary GCD algorithm

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.