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

получая правильное значение НОД. Дополнительные множители, входящие в ответ /с-арного алгоритма, называются посторонними множителями. Их размер также растет с увели­ чение к. Это также замедляет общую процедуру /с-арного алгоритма. Во второй главе подробно рассмотрен базовый /с-арный метод вычис­ ления НОД натуральных чисел и методы его ускорения. Был разработан программный комплекс по которому были проведены разные эксперимен- • тальные вычисления и сравнительный анализ результатов итерации и времени выполнения. Мы исследовали значения коэффициента редукции в зависимости от А; и поиск подходящей пары (х, у) в /с-арном алго­ ритме. Представлены методы ускорения процедуры поиска пары (х, у) и проведены экспериментальные данные по времени вычисления НОД при использовании предтаблиц обратных элементов и значений х и у. Были получены экспериментальные результаты времени при сдвиге области зна­ чений у. Еще был рассмотрен смешанный алгоритм на основе /с-арного алгоритма и схемы Евклида. В этой главе нами были получены следующие результаты: 1. Среднее количество итераций /с-арного алгоритма для чисел длины 500 десятичных разрядов уменьшается от 1358 до 573 при увеличении к от 16 до 216. Это число значительно меньше среднего числа итераций для таких пар по схеме Евклида, которое составляет 1942 итерации. 2. Среднее значение коэффициента редукции р = А /В в процессе вычисления превышает примерно в 5 раз наименьшее значение этого ко­ эффициента, обеспечиваемое теоремой Соренсона для всех к от 16 до 216. 3. Базовый /с-арный алгоритм по схеме Соренсона выполняется мед­ леннее классического алгоритма Евклида для пар чисел длины 1600 бит почти для всех значений к. Наилучшим значением является к = 16384, при котором этот алгоритм работает немного быстрее алгоритма Евклида (101 мс на 50 парах против 112 мс у алгоритма Евклида). 4. При использовании предтаблиц обратных элементов по модулю к алгоритм ускоряется от 3,8% до 9,9% в зависимости от значения к. Наи­ лучший результат (91 мс и 9,9% выигрыша) на парах длины 1600 бит достигается при к = 16384. Немного проигрывает время вычисления при к = 4096 - 94 мс. При увеличении к время опять начинает увеличиваться. 5. Те же расчеты, выполненные для чисел 3200 бит, показывают ухуд­ шение времени работы fc-арного алгоритма относительно схемы Евклида. Наилучшим средним временем на числах такой длины является время 288 мс, достигнутое при к = 16384, но даже это время проигрывает времени работы алгоритма Евклида (264 мс). Отсюда следует, что базовая версия алгоритма Соренсона даже с использованием предтаблиц работает хуже 12