Разработка эффективных алгоритмов вычисления НОД натуральных чисел для криптографии и теории чисел

- Одним из наиболее перспективных направлений, в которых быст­ рые алгоритмы НОД играют важную роль, является поиск силь­ ных псевдопростых целых чисел, что улучшает эффективность тестов простоты для криптографии111а. В первой главе еще рассматривается бинарный алгоритм вычисле­ ния НОД, который вычисляет НОД двух натуральных чисел, используя более простые арифметические операции, чем КАЕ. Он заменяет деле­ ние на арифметические сдвиги, сравнения и вычитание. Еще рассмотрены fc-арный алгоритм Евклида, который был разработан Д. Соренсоном в 1990 году и аппроксимирующий fc-арный алгоритм (новая версия Парного ал­ горитма вычисления НОД натуральных чисел, которая была разработана Ш. Ишмухаметовым в 2016 году). Вторая глава посвящена исследованию эффективного программи­ рования fc-арного алгоритма вычисления НОД двух или более целых чисел и предложим ряд модификаций, ускоряющих выполнение алгоритма. k-арный алгоритм Евклида был разработан в 1990 году Дж. Соренсо­ ном16,1 ' и улучшен независимо друг от друга Вебером14 15 * 17 18 и Джебелеаном19 в 1993 и 1995 годах. Этот алгоритм является естественным обобщением бинарного алгоритма. Основная идея алгоритма состоит в том, чтобы ис­ кать на шаге вычисления искать линейную комбинацию Ах + By заданных чисел А и В такую, что выполняется соотношение А х + B y = 0 mod к, (1) где к - заранее выбранный и фиксированный параметр алгоритма. В простейшем случае значение к равно 2, и тогда алгоритм совпада­ ет с бинарным. Значение к может быть выбрано любым положительным целым числом. Первые исследователи этого метода (Дж. Соренсон, Т. Джебелеан, К. Вебер) рассматривали разные значения этого параметра (например, Соренсон предложил выбрать к равным степени большого про­ стого числа), однако, никаких преимуществ выбор к простым, составным или степенью простого числа не давал, поэтому наилучшим вариантом стали считать значение к равным степени двойки (Вебер ). Это позволило 14Ishmukhametov Sh., Mubarakov В. On practical aspects of the Miller-Rabin Primality Test / / obachevskii Journal of Mathematics. — 2013. —Vol. 34, no. 4. — Pp. 304-312. 15Sorenson J., Webster J. Strong pseudoprimes to twelve prime bases / / Mathematics of Computation. — 2015. — Vol. 86, no. 304. — Pp. 985-1003. leSorenson J. The k-ary GCD algorithm. — University of Wisconsin-Madison, Computer Sciences Department, 1990. — Pp. 1-20. 17Sorenson J. Two fast GCD algorithms / / Journal of Algorithms. — 1994. — Vol. 16, no. 1. - Pp. 110-144. 18Weber K. The accelerated integer GCD algorithm / / ACM Transactions on Mathematical Software (TOMS). — 1995. —Vol. 21, no. 1. — Pp. 111-122. 19Jebelean T. A generalization of the binary GCD algorithm / / Proceedings of the 1993 international symposium on Symbolic and algebraic computation / ACM. — 1993. — Pp. 111-116. 10