Эффективное удаление делителей в k-арном алгоритме
Р.Р. Еникеев
Казанский (Приволжский) федеральный университет, г. Казань, 420008, Россия
Полный текст PDF
DOI: 10.26907/2541-7746.2019.3.393-404
Аннотация
Один из наиболее эффективных алгоритмов вычисления наибольшего общего делителя при работе с длинными числами – k-арный алгоритм. Вычисление наибольшего общего делителя используется во многих криптографических алгоритмах. Если при нахождении наибольшего общего делителя u, v в k-арном алгоритме бинарные длины чисел u и v близки, то используется шаг редукции t = |au + bv|/k, где 0 < a, |b| ≤ [√ k]: au + bv = 0(mod k). Если числа u и v сильно отличаются по длине, то для сокращения u до длины v испольуется операция dmod, которая определяется по формуле |u – cv|/2L, где c = uv–1mod 2L, L = L(u) – L(v), а функция L(a) – бинарная длина числа a. Ускорение k-арного алгоритма проводится путем минимизации количества операций удаления делителей в главном цикле при k = 22W, где W – длина машинного слова. Мы объединяем эту процедуру с операцией деления на 2iW, для которой описана быстрая реализация за O(1) операций, и рассматриваем новый способ вычисления коэффициентов, что в результате позволяет полностью избавиться от удаления делителей перед шагом редукции и позволяет производить удаление делителей перед операцией dmod лишь в 1/3 случаев, тем самым уменьшив общее количество операций, выполняемых над длинными числами. Предложенный нами метод ускоряет главный цикл k-арного алгоритма на 3–16% в зависимости от длины числа.
Ключевые слова: наибольший общий делитель, длинные числа, k-арный алгоритм, удаление делителей
Литература
1. Gladman B., Hart W., Moxham J., et al. MPIR: Multiple Precision Integers and Rationals. Version 2.7.0. – 2015. – URL: http://mpir.org, свободный.
2. Jebelean T. A double-digit Lehmer–Euclid algorithm for finding the GCD of long integers // J. Symbol. Computation. – 1995. – V. 19, No 1–3. – P. 145–157. – doi: 10.1006/jsco.1995.1009.
3. Stein J. Computational problems associated with Racah algebra // J. Comput. Phys. – 1967. – V. 1, No 3. – P. 397–405. – doi: 10.1016/0021-9991(67)90047-2.
4. Кнут Д. Э. Искусство программирования. Т. 2. – М.: Вильямс, 2001. – 832 c.
5. Sorenson J. Two fast GCD algorithms // J. Algorithms. – 1994. – V. 16, No 1. – P. 110–144. – doi: 10.1006/jagm.1994.1006.
6. Weber K. The accelerated integer GCD algorithm // ACM Transact. Math. Software. – 1995. – V. 21, No 1. – P. 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. – N. Y.: ACM, 1993. – P. 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. – V. 15, No 2. – P. 169–180. doi: 10.1006/jsco.1993.1012.
10. Ишмухаметов Ш.Т., Мубараков Б.Г., Камаль Маад Аль-Анни Вычисление коэффициентов Безу для k-арного алгоритма нахождения НОД // Изв. вузов. Матем. – 2017. – № 11. – С. 30–38.
11. Еникеев Р.Р. Нахождение коэффициентов Безу с помощью расширенного обобщенного бинарного алгоритма // Информационные технологии и математическое моделирование (ИТММ-2017): Материалы XVI Междунар. конф. им. А.Ф. Терпугова. – Томск: Изд-во науч.-техн. лит., 2017. – С. 284–291.
Поступила в редакцию
10.07.18
Еникеев Разиль Радикович, ассистент кафедры системного анализа и информационных технологий
Казанский (Приволжский) федеральный университет
ул. Кремлевская, д. 18, г. Казань, 420008, Россия
E-mail: renikeev@kpfu.ru
Контент доступен под лицензией Creative Commons Attribution 4.0 License.
