ملخص: The present paper analyses and presents several improvements to the algorithm for finding the (a, b)-pairs used in the k-ary reduction of the right-shift k-ary integer GCD algorithm. While the worst-case complexity of the “Accelerated integer GCD algorithm” is O((log2(k))2), we show that the worst-case number of iterations of the while loop is exactly (where ). We suggest improvements on the latter algorithm and 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.

لغة: إنجليزية