Введение в современную криптографию



Pdf көрінісі
бет238/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   234   235   236   237   238   239   240   241   ...   249
Криптография Катц

ПРЕДПОЛОЖЕНИЕ B.8 Рассмотрим выполнение GCD(a0, b0), и пусть ai, 
bi (for i = 1, . . . , A) обозначает аргументы для i-го рекурсивного вызова GCD. 
Тогда bi+2 ≤ bi/2 for 0 ≤ i ≤ A − 2.
ДОКАЗАТЕЛЬСТВО Сначала заметим, что для любого a > b имеем [a mod b] < 
a/2. Чтобы убедиться в этом, рассмотрим два случая: Если b ≤ a/2, то [a mod b] < b 
≤ a/2 является первичным. С другой стороны, если b > a/2, то [a mod b] = a − b < a/2.
Теперь зафиксируем произвольное i при 0 ≤ i ≤ A − 2. Тогда bi+2 = [ai+1
mod bi+1] < ai+1/2 = bi/2.
СЛЕДСТВИЕ B.9 В выполнении алгоритма GCD(a, b) существует не более 
2 «b» − 2 рекурсивных вызовов для GCD.
ДОКАЗАТЕЛЬСТВО Пусть ai, bi (для i = 1, . . . , A) обозначает аргументы 
для i-го рекурсивного вызова GCD. {bi} всегда больше нуля , алгоритм больше 
не делает никаких рекурсивных вызовов, если когда-либо случается, что bi =
1 (поскольку тогда bi | ai). Предыдущее предположение показывает то, что {bi} 
уменьшается на мультипликативный коэффициент (не менее) 2 за каждые две 
итерации. Отсюда следует, что количество рекурсивных вызовов для GCD не 
более 2 • («b» − 1).
Расширенный алгоритм Эвклида
Согласно предположению 8.2, что для положительных целых чисел a, b су-
ществуют целые числа X, Y при Xa + Y b = gcd(a, b). Простая модификация ал-
горитма Эвклида, называемая расширенным алгоритмом Эвклида, может быть 
использована, чтобы найти X, Y в дополнение к вычислению gcd(a, b); см. ал-
горитм B.10. Вы просили показать корректность расширенного алгоритма Эв-
клида в упражнении Exercise B.1 и доказать, что алгоритм действует в течение 
полиномиального времени в упражнении B.2.


324
 
АЛГОРИТМ B.10
Расширенный алгоритм Эвклида eGCD
Вход: Целые числа a, b при a ≥ b > 0
Выход: (d, X, Y ) при d = gcd(a, b) и Xa + Y b = d
if b делит a
return (b, 0, 1)
else
Вычислить целые числа q, r при a = qb + r и 0 < r < b (d, X, Y ) := eGCD(b, r) // 
обратите внимание, что Xb + Y r = d return (d, Y, X )


Достарыңызбен бөлісу:
1   ...   234   235   236   237   238   239   240   241   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет