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

11. Последним был предложен комбинированный метод вычисл НОД, основанный на использовании на чередовании fc-арного алгоритма и алгоритма Евклида. Теоретическая выгода такого сочетания обоснова­ на в секции 2.11, а экспериментальные подсчеты, приведенные в таблице, показывают выигрыш такого алгоритма по отношению к схеме Соренсона с предвычислениями обратных элементов по к от 10 до 18 процентов. По этой схеме было получено наилучшее значение для среднего времени вы- » числения НОД 50 пар чисел длины 1600 бит, равное 81 мс (28 процентов выигрыша у алгоритма Евклида вычисляющего НОД за 112 мс). Третья глава посвящена исследованию эффективной реализации на компьютере аппроксимирующего fc-арный алгоритм, являющегося естест­ венным обощением fc-арного алгоритма Соренсона. Этот алгоритм был разработан в 2016 году Ш.Т. Ишмухаметовым20. Главное отличие аппрок­ симирующего fc-арного алгоритма от алгоритма Соренсона заключается в выборе на шаге алгоритма пары параметров ( х,у ), обеспечивающих тож­ дество Ах + By = 0 (modfc). (2) Идея Ишмухаметова состояла в том, чтобы выбирать эти значения не перебором, а таким способом, чтобы линейная комбинация |Ах + Ву\ принимала минимальное значение. Напомним, что тождество (2) эквива­ лентно равенству у = —qx + ks, где q = A B ~ l mod fc, s € N. Варьируя значения двух параметров х и s, можно добиться высокой скорости сходимости fc-арного алгоритма, во много раз превосходящего ба­ зовую версию Соренсона. В третьей главе мы подробно исследовали аппроксимирующий fc-арный алгоритм вычисления НОД и его эффективную реализацию на языке программирования C++ в среде программирования Visual Studio с установленной библиотекой длинных чисел MPIR. Приведены теорети­ ческие расчеты. Проведены оценки производительности вычисления НОД для пар чисел различной длины по числу итераций и времени работы. Исследованы методы ускорения аппроксимирующего алгоритма и прове­ дены разные оценки времени вычисления. Были реализованы приложения этого алгоритма такие, как тест простоты Миллера-Рабина и поиск строго псевдопростых чисел по которым были проведены экспериментальные результаты. Библиотека длинных чисел MPIR является портированием под опера­ ционную систему Windows известной библиотеки длинных чисел GMP, разработанной первоначально для ОС Linux. Эта библиотека содержит тип 20Ishmukhametov Sh. An approximating fc-ary GCD algorithm / / Lobachevskii Journal of Mathematics. —2016. —Vol. 37, no. 6. — Pp. 723-729. 14