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

Общая характеристика работы Актуальность темы. Диссертационная работа посвящена решению задачи построения эффективного программного обеспечения для реа­ лизации алгоритмов вычисления НОД (наибольшего общего делителя) натуральных чисел с точки зрения их приложений к вычислениям с длинными числами, используемых в криптографии и теории чисел. Зада­ ча вычисления наибольшего общего делителя (НОД) натуральных чисел представляет собой одну из наиболее распространённые задач, имею­ щих различные приложения в современной вычислительной математике. Процедура вычисления НОД присутствует во многих криптосистемах и алгоритмах факторизации. Именно поэтому, исследование алгоритмов вы­ числения НОД является важной темой. С развитием мощных компьютеров, глобальных компьютерных сетей и информационных технологий становится более важной и задача защи­ ты информации. Криптография работает с длинными числами, выполняя задачи генерации криптографических ключей, операции шифрования и дешифрования данных. Современные криптографические алгоритмы работают с конечными полями большой размерности, выполняя многочис­ ленные модулярные вычисления. Обратные вычисления в конечных полях необходимо используют расширенный алгоритм Евклида и процедуру вы­ числения НОД в рассматриваемых алгебраических структурах. Вычисление НОД является важной фундаментальной задачей теории чисел, успешное решение которой позволяет усовершенствовать алгорит­ мы широкого класса прикладных задач, связанных с использованием современной асимметричной криптографии (алгоритмы RSA, Рабина, Эль-Гамаля, электронной цифровой подписи ЭЦП, исследование порядка эллиптической кривой)1’2, как правило, современные криптографические алгоритмы работают с длинными числами и предусматривают процедуру вычисления их НОД3’1. Наиболее распространенным из таких алгоритмов является класси­ ческий алгоритм Евклида. Однако известны и другие алгоритмы, общей целью создания которых было стремление уменьшить сложность вычисле­ ния НОД, сократить время его поиска. 1Ишмухаметов Ш.Т. Технологии защиты информации в сети, методическое пособие, Казань. — 2010. 2Рубцова Р.Г., Ишмухаметов Ш.Т. и др. Математические основы защиты информа­ ции. — 2012. 3Ishmukhametov Sh., Mubarakov В., Mochalov A. Euclidian algorithm for recurrent sequences, Applied Discrete Mathematics and Het c Journal.-Samara . — 2015. —Vol. 1, no. 2. — Pj . 5 7 -6 ^ J ^ у Щ 4Ишмухаметов Ш.Т. Методы факторизацш 2011 . fistic Algorithms / / International Scientifi Библиотека ;обие.