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

2. Были предложены и реализованы многочисленные методы модер­ низации /с-арного алгоритма, выполнены оценки их влияния на скорость выполнения алгоритма и число итераций. Среди предложенных модерни­ заций перечислим основные: 2.1. Была реализована система предвычислений, содержащая табли­ цы обратных по модулю к чисел, используемая для поиска пар чисел х,у. Это позволило добиться ускорения базового алгоритма до 25 процентов. 2.2. Были выполнены оценки средних значений коэффициента редук­ ции р = А /В на отдельных итерациях алгоритма. Полученные результаты показали, что его значение зависит только от значения параметра к и составляет величину приблизительно равную 2,5\/fc, что примерно в 5 раз превышает минимальное теоретическое значение, построенное Дж.Соренсоном. 2.3. Было доказано увеличение эффективности /с-арного алгоритм при увеличении от 16 до 214 = 16384. При дальнейшем увеличение этого па­ раметра общая эффективность алгоритма начинала ухудшаться. Поэтому оптимальным значением для /с-арного алгоритма является к — 16384. 2.4. Была разработана и реализована система предвычислений пара­ метров х,у, позволяющая выполнить поиск искомых значений параметров для каждого заданного значения к и пары значений а = A mod к и b = В mod к. Это позволило получить ускорение до 10 процентов скорости выполнения /с-арного алгоритма для к < 1024). Однако, при увеличении к эффективность алгоритма падала, объем таких таблиц стал слишком большой (для к = 16384 составляем более гегабайта объема), поэтому в целом эта модернизация была признана не эффективной и в дальнейшем не использовалась. 2.5. Был разработан и реализован алгоритм сдвига области изменения параметров ( х,у ), который позволил получить до 25 процентов ускорения без какого-то существенного изменения выполняемых кодов. 2.6. Были проанализировано изменение коэффициента редукции р = А /В на отдельных итерациях алгоритма и выяснено, что происходит чере­ дование итераций с небольшим значением р и итерациями, на которых р получает большие значения. Для уменьшения таких провалов был предло­ жен новый модифицированный комбинированный алгоритм, чередующий использование на нечетных шагах /с-арного алгоритма с алгоритмом Ев­ клида, выполняемым на четных шагах. Такой алгоритм оказался самым эффективным из всех предложенных модификаций, с^та модификация ра­ ботает примерно на 30 процентов быстрее алгоритма Евклида. 19