ПРЕДПОЛОЖЕНИЕ 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 )
Достарыңызбен бөлісу: |