Improvements on the accelerated integer GCD algorithm

Abstract

The present paper analyses and presents several improvements to the algorithm for finding the $(a,b)$-pairs of integers used in the $k$-ary reduction of the right-shift $k$-ary integer GCD algorithm. While the worst-case complexity of Weber's "Accelerated integer GCD algorithm" is $\cOł(\log_ϕ(k)^2\r)$, we show that the worst-case number of iterations of the while loop is exactly $\frac{1}{2}ł\lfloor {\log }_{\varphi }(k)\mathring{\rfloor }$, where $\varphi :=\frac{1}{2}ł(1+\sqrt{5}\mathring{)}$.\par We suggest improvements on the average complexity of the latter algorithm and also present two new faster residual algorithms: the sequential and the parallel one. A lower bound on the probability of avoiding the while loop in our parallel residual algorithm is also given.

6 pages