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

Одним из самых перспективных таких алгоритмов является fc-арный алгоритм поиска GCD, опубликованный в 1990-х годах Джонатаном Со­ ренсоном ^ . По сравнению с классическим алгоритмом Евклида данный алгоритм позволяет заметно снизить время вычислений при аккурат­ ном выборе параметра к. В дальнейшем самим Соренсоном и другими учёными было предложено несколько вариантов улучшения и модифика­ ции fc-арного алгоритма5 6 7 89’'*’10. Одним из них является аппроксимирующий /с-арный алгоритм, предложенный проф. Ш.Т. Ишмухаметовым11. Цель работы. Целью данной работы является сравнительное иссле­ дование трех алгоритмов вычисления НОД длинных натуральных чисел: классического алгоритма Евклида, /с-арного алгоритма Дж. Соренсона, ап­ проксимирующего fc-арного алгоритма Ш.Т. Ишмухаметова и разработки эффективного программного обеспечения для реализации этих алгоритмов и ускорения операций вычисления наибольшего общего делителя с длин­ ными целыми числами. Степень разработанности темы. Задача сравнительного изуче­ ния трех алгоритмов вычисления НОД и построения эффективного про­ граммного обеспечения для их выполнения выполнена в полном объеме. Разработан пакет программ, реализующий базовые версии рассматри­ ваемых алгоритмов, система тестирования, генерирующая пары чисел заданной длины и выполняющая контроль значений различных парамет­ ров вычисления таких, как время выполнения всей процедуры, среднее и максимальное число итераций для каждого из рассмотренных алгоритмов и наборов пар чисел заданной длины от 100 до 3000 бит, влияние различ­ ных методов ускорения на сходимость процедуры вычисления НОД. С помощью этих программ были получены численные оценки сходи­ мости трех рассматриваемых алгоритмов для различных входных наборов данных, выведены точные оценки времени выполнения процедуры вычис­ ления НОД и числа итераций, доказана эффективность использования к -арного алгоритма Соренсона КАРИ и аппроксимирующего алгоритма 5Sorenson J. The k-ary GCD algorithm. — University of Wisconsin-Madison, Computer Sciences Department, 1990. — Pp. 1-20. 6Sorenson J. Two fast GCD algorithms / / Journal of Algorithms. — 1994. —Vol. 16, no. 1. - Pp. 110-144. 7Sorenson J.P. An analysis of the generalized binary GCD algorithm / / High Primes and Misdemeanors: Lectures in Honour of the 60th Birthday of Hugh Cowie Williams. — 2004. — Pp. 327-340. 8Weber K. The accelerated integer GCD algorithm / / ACM Transactions on Mathematical Software (TOMS). — 1995. —Vol. 21, no. 1. — Pp. 111-122. 9Jebelean T. A generalization of the binary GCD algorithm / / Proceedings of the 1993 international symposium on Symbolic and algebraic computation / ACM. — 1993. — Pp. 111-116. 10Wang X., Pan V.Y. Acceleration of Euclidean algorithm and rational number reconstruction / / SIAM Journal on Computing. — 2003. —Vol. 32, no. 2. — Pp. 548-556. n Ishmukhametov Sh. An approximating k-ary GCD algorithm / / Lobachevskii Journal of Mathematics. — 2016. —Vol. 37, no. 6. — Pp. 723-729. 4