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

5. Выполнены серии вычислений НОД с использованием различных значений длин входных чисел, параметра к и различных ускоряющих при­ емов для оптимальной сходимости всего алгоритма. 6. Подсчитаны среднее и общее число итераций, наилучшее время для каждого из входных наборов исходных данных, значения параметра к и реализаций тех или иных процедур аппроксимирующего алгоритма. Результаты вычислений собраны в таблицы. 7. Доказано абсолютное превосходство аппроксимирующего алго­ ритма при выборе оптимальных параметров вычисления при различных длинах исходных чисел от 100 до 1000 десятичных разрядов у алгоритмов Евклида и к —арного алгоритма Соренсона как по числу итераций, так и по времени вычислений. По числу итераций аппроксимирующий алго­ ритм обгоняет алгоритм Евклида до 5 раз и комбинированный fc-арный алгоритм до двух раз, а по времени - до трех раз. 8. Был реализован эффективный поиск строго псевдопростых чисел на основе аппроксимирующего алгоритма, с помощью которого были най­ дены все строго псевдопростые числа, меньшие 1012, включая числа ч/х, и фв из последовательности {фп }п, в настоящее время построенной до члена ч/Дз (J. Sorenson, J. Webster)21. Этим доказана высокая эффективность аппрок­ симирующего алгоритма, выполняющего подобные вычисления примерно в три раза быстрее классического алгоритма Евклида, который обычно используется в подобных вычислениях. В заклю чении приведены основные выводы по диссертации, сфор­ мулированы полученные научные и практические результаты, которые заключаются в следующем: 1. Разработана эффективная реализация /с-арного алгоритма Дж. С ренсона. Для реализации этой цели была построена система тестирования, содержащая большой набор тестовых пар чисел различной длины от 100 до 3000 бит, программное обеспечение на языке C++ на основе программ­ ной среды MS Visual Studio 2012 и библиотеки длинных чисел MPIR для выполнения операций вычисления наибольшего общего делителя и систе­ мой контроля влияния отдельных параметров на ход процедуры, системы оценки качества разрабатываемых алгоритмов, оценивающая общее и сред­ нее число итераций, требуемых для вычисления НОД для наборов пар натуральных чисел, обще е и среднее время выполнения в сравнении для классического алгоритма Евклида. 21Sorenson J., Webster J. Strong pseudoprimes to twelve prime bases / / Math ematics of Computation. — 2015. —Vol. 86, no. 304. — Pp. 985-1003. 18