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

AKA для решения практических задач теории чисел и криптографии. Так­ же определен новый комбинированный алгоритм КОМБИ, соединяющий простоту классического алгоритма Евклида и достоинства /с-арного алго­ ритма и выполняющийся быстрее обоих алгоритмов. Для достижения поставленной цели были решены следующие задачи: 1. Выполнен анализ современных алгоритмов вычисления НОД нату­ ральных чисел —классического алгоритма Евклида КАЕ, бинарно­ го алгоритма Стейна, /с-арного алгоритма и аппроксимирующего /с-арного алгоритма; 2. Разработан программный комплекс для выполнения полноценного тестирования всех трех рассматриваемых в диссертации алгорит­ мов, оценки влияния входных и промежуточных параметров на скорость выполнения процедуры, число итераций и время, затра­ чиваемое на каждой итерации и всей процедуры в целом. 3. Разработаны эффективные реализации алгоритмов вычисления НОД с использованием библиотеки длинных чисел MPIR12 в среде Visual Studio, на основе современных принципов программирова­ ния; 4. Выполнены экспериментальные вычисления и сбор статистическо­ го материала по скорости выполнения этих алгоритмов и числу итераций в зависимости от выбора параметров; 5. Выполнено ускорение алгоритмов вычисления НОД на основе под­ бора эффективных параметров и использования предтаблиц; 6. Разработаны практические приложения алгоритмов для решения сложных вычислительных задач (поиска строго псевдопростых чи­ сел для ускорения теста простоты Миллера-Рабина. Научная новизна: Аппроксимирующий /с-арный алгоритм являет­ ся современным эффективным алгоритмом вычисления НОД, разработан­ ный Ш.Т. Ишмухаметовым. До настоящего времени не было ни одной полной реализации этого алгоритма для работы с длинными числами. Так­ же никем не выполнялось сравнительное тестирование этого алгоритма в сравнении с другими известными алгоритмами вычисления НОД. Эта работа была выполнена впервые в нашей диссертации. Нами доказано аб­ солютное превосходство данного алгоритма над классическим алгоритмом Евклида и /с-арным алгоритмом Соренсона путем выполнения эксперимен­ тальных вычислений с числами различной длины. Также нами были разработаны методы, ускоряющие выполнение этого алгоритма с использованием особенностей представления длинных чисел в библиотеке MPIR и использования рядов Фарея для аппроксима­ ции параметра а, играющего основную роль в этом алгоритме. 12Torbjorn Granlund and the GMP Development Team. The Multiple Precision Integers and Rationale Library Edition 2. — 2015. — URL: http://mpir.ol ‘g/mpir-2.7.2.pdf 5