On acceleration of the k-ary GCD algorithm

I. Amer ^∗, S.T. Ishmukhametov^∗∗

Kazan Federal University, Kazan, 420008 Russia

E-mail:  ^∗safadi121979@yahoo.com,  ^∗∗sishmukh@kpfu.ru

Received June 15, 2018

Full text PDF

DOI: 10.26907/2541-7746.2019.1.110-118

For citation Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki vol. 161, no. 1, pp. 110–118. doi: 10.26907/2541-7746.2019.1.110-118. (In Russian) : Amer I., Ishmukhametov S.T. On acceleration of the k-ary GCD algorithm. , 2019

Abstract

In this paper, methods of acceleration of GCD algorithms for natural numbers based on the k-ary GCD algorithm have been studied. The k-ary algorithm was elaborated by J. Sorenson in 1990. Its main idea is to find for given numbers A, B and a parameter k, co-prime to both A and B, integers x and y satisfying the equation Ax + By ЃЯ 0 mod k Then, integer C = (Ax + By)/k takes a value less than A. At the next iteration, a new pair (B,C) is formed. The k-ary GCD algorithm ensures a significant diminishing of the number of iterations against the classical Euclidian scheme, but the common productivity of the k-ary algorithm is less than the Euclidian method.

 We have suggested a method of acceleration for the k-ary algorithm based on application of preliminary calculated tables of parameters like as inverse by module k. We have shown that the k-ary GCD algorithm overcomes the classical Euclidian algorithm at a sufficiently large k when such tables are used.

 Keywords: greatest common divisor for natural numbers, Euclidian GCD algorithm, binary GCD algorithm, k-ary GCD algorithm

Acknowledgments. This work was funded by the subsidy allocated to Kazan Federal University for the state assignment in the sphere of scientific activities, project no. 1.13556.2019/13.1. The study was also supported in part by the Russian Foundation for Basic Research (project no. 18-47-16005).

References

1. Ishmukhametov Sh.T. Metody faktorizatsii natural'nykh chisel [Methods of Factorization of Positive Integers]. Kazan, Izd. Kazan. Univ., 2011. 189 p. (In Russian)

2. Ishmukhametov Sh.T., Mubarakov B.G., Maad Kamal Al-Anni 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.

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. The Art of Computer Programming. Vol. 2: Seminumerical Algorithms. Addison-Wesley, 1997. xiv, 762 p.

5. Ishmukhametov S.T. Rubtsova R.G. A parallel computation of the GCD of natural numbers. Parallel'nye vychislitel'nye tekhnologii – XI mezhdunarodnaya konferentsiya, PaVT' 2017 [Parallel Computational Technologies: XI Int. Conf., PCT' 2017]. Kazan, 2017, pp. 120–129. (In Russian)

6. Sorenson J. The k-ary GCD Algorithm: Computer Sciences Technical Report CS-TR-90-979. Madison, Univ. of Wisconsin, 1990. 20 p.

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

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

9. Ishmukhametov S.T. An approximating k-ary GCD algorithm. Lobachevskii J. Math., 2016, vol. 37, no. 6, pp. 723–729. doi: 10.1134/S1995080216060147.

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

11. Maximov K.L., Ishmukhametov S.T. About algorithm of smooth numbers calculation. Res. J. Appl. Sci., 2015, vol. 10, no. 8, pp. 376–380.

12. Ishmukhametov S.T., Mubarakov B.G. On practical aspects of the Miller–Rabin Primality Test. Lobachevskii J. Math., 2013, vol. 34, no. 4, pp. 304–312. doi: 10.1134/S1995080213040100.

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