Efficient removal of divisors in the $k$-ary algorithm

R. R. Enikeev

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

Résumé

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.

Détail

Keywords: greatest common divisor, $k$-ary algorithm, factors removal, multi-precision integers.