Efficient removal of divisors in the k-ary algorithm

Abstract

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 = |au + bv|/k, where 0 < a, |b| ≤ [√ k]: au + bv = 0(mod k). The reduction step is used when and have almost the same size. Otherwise, we appled the dmod operation |u – cv|/2L, where c = uv–1mod 2L, 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 = 22W, 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 2iW 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.

Keywords

• greatest common divisor
• k-ary algorithm
• factors removal
• multi-precision integers