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

ускорить выполнение рутинных операциях на шагах алгоритма, поскольку деление на степень двойки означало просто сдвиг числа вправо. Итак, пусть к - четная степень двойки, например, к = 2т , и А > В > 0 - нечетные целые числа. В главе 1 была сформулирована и доказана основная теорема Соренсона, служащая базисом /с-арного алгоритма: Теорема 1. (Дж.. Соренсон [1990]). Пусть т > 1 - фиксированное натуральное число, к = то2. Д ля любых целых чисел А и В , А > В > О, взаимно простых с то, существуют ненулевые х , у , |т|, |у| < то такие, что выполняется соотношение (1). Следуя теореме Соренсона, на шаге алгоритма для фиксированного к и заданных нечетных А п В вычисляются коэффициенты х ,у , удовле­ творяющие теореме, и вычисляется С — (Ах + B y )/к . Далее вычисляется d =НОД(С, то), и если он не равен 1, то выполняется сокращение С на d, пока С не станет взаимно простым с то. В завершении итерации пара (А,В) заменяется парой (В,С), которая имеет меньший размер по сравне­ нию с исходной парой. Назовем отношение большего числа к меньшему в паре (Л; В) на ша­ ге алгоритма коэффициентом редукции и обозначим символом р = А /В . Чем больше среднее значение этого коэффициента, тем быстрее сходит­ ся алгоритм. Согласно теореме Соренсона: А _ Ак Ак _ у/к С Ах + By _ 2 А\[к 2 откуда и 1/4 р = у /А /С > —=г « 0,707 к1/А. v2 Таким образом, что при увеличении к в 16 раза, нижняя граница для р увеличивается в два раза. Значение к можно брать большим, оставаясь в размере одного машин­ ного слова (до 264), однако экспериментальные вычисления, которые мы приведем в этой главе, показывают, что скорость алгоритма оптимальна при значениях к от к = 1024 до к = 4096. При дальнейшем увеличении к поиск подходящей пары (х,у) и выполнение промежуточных вычислений выполняется дольше, что замедляет выполнение алгоритма в целом. Кроме того, поскольку НОД d, вычисленный в fc-арном алгоритме не обязательно равен исходному НОД (Л, В) = do, а является его кратным. По­ этому после завершения процедуры вычисления НОД с помощью fc-арного алгоритма и получения его ответа d, необходимо выполнить дополнитель­ ное вычисление, используя алгоритм Евклида d0 = GCD(A\ GCD(B,d)) 11 /