Авторы

Альхалиди А.М., АльТулайхи Мукдад Мухаммид Усман

Аннотация

В нашей статье мы рассмотрим модификации выбора коэффициентов x и y в k-арном алгоритме для вычисления наибольшего общего делителя НОД заданных длинных натуральных чисел A и B на основе k-арного алгоритма, и анализируем метод его ускорения. Задача вычисления НОД играет важную роль в разных сферах теории чисел и криптографии такие, как арифметические операции в конечных полях и генерации ключей для криптографии.

Ключевые слова

наибольший общий делитель НОД, бинарный алгоритм, К-арный алгоритм.

Статья

УДК​​ 511.1

 

Ускорение и разработка k-арного алгоритма для расчета НОД

 

Альхалиди А.М.1,​​ АльТулайхи Мукдад Мухаммид Усман2

 

Казанский федеральный университет1

Ульяновск государственной технически университет2

 

В нашей статье мы рассмотрим модификации выбора коэффициентов x и y в k-арном алгоритме для вычисления наибольшего общего делителя НОД заданных длинных натуральных чисел A и B на основе k-арного алгоритма, и анализируем метод его ускорения. Задача вычисления НОД играет важную роль в разных сферах теории чисел и криптографии такие, как арифметические операции в конечных полях и генерации ключей для криптографии.

 

Ключевые слова:​​ наибольший общий делитель НОД, бинарный алгоритм,​​ 

К-арный алгоритм.

 

Введение

 

Целью данного исследования является разработка и программирование различных алгоритмов для вычисления НОД, которые широко используются в криптографических алгоритмах и теориях чисел. (см. [1]).

K-арный алгоритм является бинарным алгоритмом для расчета НОД и был разработан американским математиком одновременно в начале 1990-х годов Дж. Соренсоном [2], [3] и австрийским Т. Джебелеаном [4].

 

Практический аспект

 

Теорема (Д. Соренсон [2]).​​ Задача для расчета НОД для нормальных чисел​​ A,B и k>1, взаимно-простого с​​ A и B, найдутся Натуральные числа​​ x и y.​​ 1x<k, -kyk, и​​ 

 

Ax+By0 (mod k)​​ (1)

 

Из (1) следует, что​​ y-AB-1x mod k. ​​ Вы можете найти пару необходимых чисел x и y, посмотрев на значения x от 1 до и​​ k соответственно и рассчитав отрицательные и положительные важные значения, чтобы получить указанное значение y = -qx mod k и​​ y=k-(qx mod k), Таким образом, y находится из интервала [-√k; √k]. Чтобы ускорить k-арный алгоритм, начальные вычисления значений (x, y) могут быть сделаны для каждого значения q <k. Состоит из отдельной итерации алгоритма, Мы учимся, как получить меньше этих итераций и следовательно при хорошей реализации с​​ параллелизацией вычисления можно​​ ускорить время Фактический алгоритм работы для вычисления НОД. ​​ 

Для этого мы используем значение от​​ t=0 до (2k) ​​ ​​​​ для разных k, где t - числовой интервал сдвига коэффициента y (см. [5]). Следующий раздел иллюстрирует наши различные экспериментальные данные в таблицах (таблицы 1,2) и в виде важных графиков (рисунки 1,2,3) для серии вычислений из 60 пар чисел длиной 1600 натуральных десятичных цифр для оценки количества​​ фактических итераций и фактического времени выполнения алгоритма вычисления. K-арый​​ НОД.

 

Результаты и обсуждение

 

Таблица 1 содержит итерации до использования сдвига​​ t​​ и минимальные итерации с использованием разных значений параметра​​ t​​ сдвига​​ интервала коэффициента ​​ y​​ для 60 пар длины 1600 десятичных разрядов при разных​​ k.

 

Таблица 1.​​ Оценка​​ частоты​​ вычислений НОД для целочисленных пар​​ Длины 1600 знаков после запятой для натуральных чисел в зависимости от​​ k

Параметр k

Итерация до сдвига​​ t

Минимальная итерация с сдвигом​​ t

16

1351.9

1255.7

256

1012.1

946.8

4096

794

760

65536

657.7

631.7

262144

601.1

583

 

Мы видим что, число итерации уменьшается с ростом параметра​​ k, и​​ минимальная итерация (оптимум) получается при​​ k=262144. Cледовательно в таблице 2 показано время (в миллисекундах) работы​​ k–арного алгоритма вычисления НОД, для 60 пар длины 1600 десятичных разрядов до и после использования сдвига​​ t.

 

Таблица​​ 2.​​ Оценка скорости Рассчитать НОД для натуральных целочисленных пар Длины 1600 знаков после запятой для натуральных чисел в зависимости от​​ k.

Параметр k

Время до сдвига​​ t

Минимальное время с сдвигом​​ t

16

258

229

256

192

174

4096

173

153

65536

145

140

262144

143

135

 

Мы видим что, время работы ​​ k–арного алгоритма​​ тоже уменьшается с ростом параметра​​ k, и​​ минимальное время (оптимум) получается при​​ k=262144.

Ниже приведены наши графики в виде гистограмме​​ (Рисунки 1,2) для оценки итерации и времени вычисления НОД в​​ k-арном алгоритме до и после сдвига​​ интервала коэффициента​​ y.

 

Рис. 1.​​ Сравнение числа Итерации вычисления НОД для пар натуральных целых чисел с 1600 длинами натуральных десятичных чисел в зависимости от​​ k​​ до и после​​ t​​ сдвига​​ интервала коэффициента​​ y.

 

Из рисунка 1 видно что, при​​ k=262144​​ получается оптимум итерации (583). А на следующем рисунке приведено время вычисления НОД.

 

Рис. 2.​​ Сравнение Время очень важно для расчета НОД для правильных цифр​​ вых пар длиной 1600 натуральных десятичных знаков в зависимости от​​ k​​ до и после​​ t​​ сдвига​​ интервала коэффициента​​ y.

 

Из рисунка 2 видно что, при​​ k=262144​​ с использованием​​ t​​ получается оптимум времени (135​​ ms) работы​​ k-арного алгоритма в нашей реализации.

На следующем рисунке как пример нашей реализации приведем полный график, изображающий время вычисления НОД в​​ k-арном алгоритме, для 60 пар длины 1600 десятичных разрядов,​​ при​​ k=256​​ с использованием разных значений​​ t(от 0 до 32).​​ 

 

Рис. 3. ​​​​ Время вычисления НОД для 60 пар длины 1600 десятичных разрядов​​ при​​ k=256, в зависимости от​​ t​​ сдвига​​ интервала коэффициента​​ y.

 

Из рисунка 3 видно что, при​​ k=256 ​​​​ с разными значениями​​ t​​ оптимум времени будет равен (174​​ ms), и это получается при​​ t=21.​​ 

 

Выводы

 

Обратите внимание, что со сдвигом t в интервале коэффициента y и отличным выбором​​ ​​ k, итерации и время вычисления НОД длинных натуральных чисел в k-арном алгоритме могут быть ясно видны. Это облегчает нам возможность работать и вычислять скорость НОД [6], что очень важно и актуально, чтобы иметь множество численных приложений в теориях шифрования и настройки.

 

Список​​ литературы

 

  • Ш. Т. Ишмухаметов, «Методы факторизации натуральных чисел: учебное пособие»​​ 2011, 190 с.

  • Sorrenson J. The k-ary GCD Algorithm, 1990, Univ.Wisc-Madison Tecn.Report,20p.

  • Sorrenson J. Two fast GCD Algorithms, 1994, J.Alg. 16, N1, pp. 110-144.

  • Jebelean T. A generalization of the binary GCD algorithm. InProceedings of the 1993 international symposium on Symbolic and algebraic computation 1993 Aug 1 (pp. 111-116). ACM.

  • Amer Ismail F. Selecting the interval of the coefficient​​ y​​ of the k-ary GCD algorithm for natural numbers //Recent trend in Science and Technology management. – 2018.

  • Ishmukhametov S. An approximating k-ary GCD algorithm. Lobachevskii Journal of Mathematics. 2016 Nov 1;37(6):723-9.

References

 

  • Ishmukhametov ​​ S.T. ​​ The ​​ factorization ​​ methods ​​ for ​​ natural ​​ numbers, ​​ Kazan, ​​ Russia, 2011, 190 p.​​ 

  • Sorrenson J. The k-ary GCD Algorithm, 1990, Univ.Wisc-Madison Tecn.Report,20p.

  • Sorrenson J. Two fast GCD Algorithms, 1994, J.Alg. 16, N1, pp. 110-144.

  • Jebelean T. A generalization of the binary GCD algorithm. InProceedings of the 1993 international symposium on Symbolic and algebraic computation 1993 Aug 1 (pp. 111-116). ACM.

  • Amer Ismail F. Selecting the interval of the coefficient​​ y​​ of the k-ary GCD algorithm for natural numbers //Recent trend in Science and Technology management. – 2018.

  • Ishmukhametov S. An approximating k-ary GCD algorithm.. 2016 Nov 1;37(6):723-9.

©​​ А.М.​​ Альхалиди,​​ АльТулайхи​​ Мукдад​​ Мухаммид​​ Усман, 2019

Скачать PDF

Выходные данные

Альхалиди А.М., АльТулайхи Мукдад Мухаммид Усман Ускорение и разработка k-арного алгоритма для расчета НОД [Электронный ресурс] // Вестник современных исследований. — Электрон. журн. — 2019. — № 10. — Режим доступа: https://orcacenter.ru

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *