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 |
| Summary: | 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. |
|---|---|
| ISSN: | 2541-7746 2500-2198 |