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

Основные достижения диссертации содержатся в следующем пе­ речне: 1. Разработан программный комплекс, реализующий рассмотренные алгоритмы и выполняющий оценки их эффективности на языке программирования язык C++ в среде Visual Studio с использова­ нием библиотеки длинных чисел MPIR); 2. Найдены оптимальные значения параметров, обеспечивающих быстрое выполнение fc-арного и аппроксимирующего алгоритмов для пар чисел различной длины; 3. Доказано практическое ускорение процедуры вычисления НОД с использованием Агарного и аппроксимирующего А-арного ал­ горитмов по отношению к классическому алгоритму Евклида и бинарному алгоритму; 4. Выполнено исследование скорости сходимости Ас-арного алгоритма Соренсона при сдвиге области значений параметров х, у, найде­ ны оптимальные параметры и доказано практическое ускорение /с-арного алгоритма до 20 5. Выполнены экспериментальные оценки скорости вычисления НОД для чисел различной разрядности для аппроксимирующего Ас-арного алгоритма, получены численные результаты сходимости этих алгоритмов в виде таблиц и графиков по числу итераций и времени вычислений для чисел различной длины до 2000 десятич­ ных разрядов (примерно, 6500 бит). 6. Разработан новый комбинированный алгоритм КОМБИ вычис­ ления НОД, основанный на сочетании на разных итерациях алгоритмов Евклида и fc-арного алгоритма, работающий до двух раз быстрее, чем исходные алгоритмы Евклида и Соренсона. Теоретическая и практическая значимость работы. В диссер­ тации были исследованы и построены новые эффективные версии ал­ горитмов вычисления НОД на основе алгоритмов Евклида, Соренсона и Ишмухаметова. Эти алгоритмы могут быть использованы в крипто­ графии, теории чисел и других численных разделах математики при генерации параметров криптосистем с открытым ключом (RSA), при по­ иске нетривиальных делителей натуральных чисел (факторизации чисел), при построении электронной цифровой подписи ЭЦП, построении архивов типа блокчейн и решении других задач с числами большой размерности. Методология и методы исследования. При выполнение работы использовались методы теории чисел, арифметические операции в конеч­ ных полях, теории алгоритмов, библиотека длинных чисел MPIR в Visual studio и компьютерного моделирования. Основные положения, выносимые на защиту: 6