Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ОКАЗАТЕЛЬСТВО
- СЛЕДСТВИЕ B.9
- Расширенный алгоритм Эвклида
| ПРЕДПОЛОЖЕНИЕ 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 ) жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|