Efficient removal of divisors in the k-ary algorithm

R.R. Enikeev

Kazan Federal University, Kazan, 420008 Russia
E-mail: renikeev@kpfu.ru
Received July 10, 2018

Full text pdf

DOI: 10.26907/2541-7746.2019.3.393-404

For citation: Enikeev R.R. Efficient removal of divisors in the k-ary algorithm. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 3, pp. 393–404. doi: 10.26907/2541-7746.2019.3.393-404. (In Russian)

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|/2^L, where c = uv^–1mod 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^iW 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

References

1. Gladman B., Hart W., Moxham J., et al. MPIR: Multiple Precision Integers and Rationals. Version 2.7.0, 2015. Available at: http://mpir.org.

2. Jebelean T. A double-digit Lehmer–Euclid algorithm for finding the GCD of long integers. J. Symbol. Comput., 1995, vol. 19, nos. 1–3, pp. 145–157. doi: 10.1006/jsco.1995.1009.

3. Stein J. Computational problems associated with Racah algebra. J. Comput. Phys., 1967, vol. 1, no. 3, pp. 397–405. doi: 10.1016/0021-9991(67)90047-2.

4. Knuth D.E. Iskusstvo programmirovaniya [The Art of Computer Programming]. Vol. 2: Seminumerical algorithms. Moscow, Vil'yams, 2001. 832 p. (In Russian)

5. Sorenson J. Two fast GCD algorithms. J. Algorithms, 1994, vol. 16, no. 1, pp. 110–144. doi: 10.1006/jagm.1994.1006.

6. Weber K. The accelerated integer GCD algorithm. ACM Transact. Math. Software, 1995, vol. 21, no. 1, pp. 111–122. doi: 10.1145/200979.201042.

7. Jebelean T. A generalization of the binary GCD algorithm. Proc. 1993 Int. Symp. on Symbolic and Algebraic Computation. New York, ACM, 1993. pp. 111–116. doi: 10.1145/164081.164102.

 8. Shoup V. A Computational Introduction to Number Theory and Algebra. Cambridge, Cambridge Univ. Press, 2008. 598 p.

9. Jebelean T. An algorithm for exact division. J. Symbol. Comput., 1993, vol. 15, no. 2, pp. 169–180. doi: 10.1006/jsco.1993.1012.

10. Ishmukhametov Sh.T., Mubarakov B.G., Kamal Al-Anni Maad Calculation of Bezout's coefficients for the k-ary algorithm of finding GCD. Russ. Math., 2017, vol. 61, no. 11, pp. 26–33. doi: 10.3103/S1066369X17110044.

11. Enikeev R.R. Computing Bezout coefficients using extended generalized binary algorithm. Informatsionnye tekhnologii i matematicheskoe modelirovanie (ITMM-2017): Materialy XVI Mezhdunar. konf. im. A.F. Terpugova [Information Technology and Mathematical Modeling (ITMM-2017): Proc. XVI Int. Conf. Dedicated to A.F. Terpugov]. Tomsk, Izd. Nauchn.-Tekh. Lit., 2017, pp. 284–291. (In Russian)

The content is available under the license Creative Commons Attribution 4.0 License.