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

алгоритма Евклида при длине входных аргументов больше примерно 3000 бит. 6. Однако для чисел длины меньше 3000 бит (напомним, что стандарт­ ные длины ключей RSA составляют 1024 и 2048 бит) алгоритм Соренсона обгоняет алгоритм Евклида. Время выполнения этих алгоритмов на чис­ лах 640 бит доказывает преимущество fc-арного алгоритма по отношению к алгоритму Евклида почти для всех к, а при к — 4096 выполняется за 25 мс против 34 мс у алгоритма Евклида (выигрыш составляет 26,5%). 7. Исследован метод непосредственного анализа значений параметра q = А В ~ г mod к для ускорения вычисления коэффициентов (х,у). Однако, данный алгоритм не дал значительного ускорения вычисления и в даль­ нейшем не рассматривался. 8. Также был исследован метод использования предтаблиц для прямого нахождения коэффициентов (х,у) по значению параметра q — AB_1 mod к. Этот подход требует значительного объема машинной памя­ ти, так как необходимо хранить таблицы, содержащие примерно У 4 строк, что при больших к становится не эффективным. Однако при к = 4096 мы смогли достичь более быстрого вычисления НОД 50 пар чисел длины 1600 бит, равной 85 мс. 9. Далее нами был исследован метод сдвига параметра у, заключаю­ щийся в том, что вместо интервала [—Vk;Ук] подходящее значение у мы искали в сдвинутом влево интервале [—Ук—t;Ук—t]. При подходящем зна­ чении t параметры х и у имеют противоположные знаки, что обеспечивает уменьшение значения линейной комбинации \Ах + Ву\. Этот метод хорошо тем, что не требует никаких значительных изменений в алгоритме, а про­ сто изменения границ в процедуре поиска значений коэффициентов ( х ,у ). Сначала мы рассмотрели небольшие значения к и сдвиги t < 2 Ук на числах длины 1600 бит. При таких ограничениях получено небольшое ускорение (до 12,8%) при к = 16 и t = 5 (то есть у искался на интервале [—9; —1] вместо [-4; 4]). При следующем значении к = 64 удалось достичь только 3-х про­ центного выигрыша при t = 3. Поэтому при к > 256 сдвиг на небольшие значения t является неэффективным. 10. Следующими был рассмотрен метод сдвига на большой интервал, сравнимый по величине с параметром к. В этом случае рассматривались различные значения к и пары чисел различной длины. Общий выигрыш, полученный от таких сдвигов, зависит как от вели­ чины сдвига, так и от длины исходных чисел. Наилучший результат для пар длины 4800 бит был достигнут при сдвиге на величину половины к и составит примерно 25 процентов. 13