Efficient removal of divisors in the k-ary algorithm
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. Otherwis...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Kazan Federal University
2019-09-01
|
| Series: | Учёные записки Казанского университета. Серия Физико-математические науки |
| Subjects: | |
| Online Access: | https://kpfu.ru/uz-eng-phm-2019-3-6.html |
| _version_ | 1797965754514014208 |
|---|---|
| author | R.R. Enikeev |
| author_facet | R.R. Enikeev |
| author_sort | R.R. Enikeev |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-11T02:05:00Z |
| format | Article |
| id | doaj.art-46a44dd5dd0d43e0b882e8006f654908 |
| institution | Directory Open Access Journal |
| issn | 2541-7746 2500-2198 |
| language | English |
| last_indexed | 2024-04-11T02:05:00Z |
| publishDate | 2019-09-01 |
| publisher | Kazan Federal University |
| record_format | Article |
| series | Учёные записки Казанского университета. Серия Физико-математические науки |
| spelling | doaj.art-46a44dd5dd0d43e0b882e8006f6549082023-01-03T03:14:41ZengKazan Federal UniversityУчёные записки Казанского университета. Серия Физико-математические науки2541-77462500-21982019-09-01161339340410.26907/2541-7746.2019.3.393-404Efficient removal of divisors in the k-ary algorithmR.R. Enikeev0Kazan Federal University, Kazan, 420008 RussiaThe 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.https://kpfu.ru/uz-eng-phm-2019-3-6.htmlgreatest common divisork-ary algorithmfactors removalmulti-precision integers |
| spellingShingle | R.R. Enikeev Efficient removal of divisors in the k-ary algorithm Учёные записки Казанского университета. Серия Физико-математические науки greatest common divisor k-ary algorithm factors removal multi-precision integers |
| title | Efficient removal of divisors in the k-ary algorithm |
| title_full | Efficient removal of divisors in the k-ary algorithm |
| title_fullStr | Efficient removal of divisors in the k-ary algorithm |
| title_full_unstemmed | Efficient removal of divisors in the k-ary algorithm |
| title_short | Efficient removal of divisors in the k-ary algorithm |
| title_sort | efficient removal of divisors in the k ary algorithm |
| topic | greatest common divisor k-ary algorithm factors removal multi-precision integers |
| url | https://kpfu.ru/uz-eng-phm-2019-3-6.html |
| work_keys_str_mv | AT rrenikeev efficientremovalofdivisorsinthekaryalgorithm |