Розширений алгоритм Евкліда

Розширений алгоритм Евкліда — це розширення алгоритму Евкліда. Окрім знаходження найбільшого спільного дільника для цілих a і b, як це робить алгоритм Евкліда, він також знаходить цілі x і y (одне з яких зазвичай від'ємне), які задовольняють рівнянню Безу.

$ax+by=\gcd(a,b).$

Розширений алгоритм Евкліда особливо корисний коли a і b взаємно прості числа, бо x — обернене щодо a за модулем b, а y — обернене щодо b за модулем a.

Неформальне визначення алгоритму

Ділене	Дільник	Частка	Остача
120	23	5	5
23	5	4	3
5	3	1	2
3	2	1	1
2	1	2	0

Для пояснення алгоритму Евкліда, розглянемо обчислення НСД(120, 23), що показано на таблиці ліворуч.

В цьому випадку, остача в четвертому рядку (дорівнює 1) показує, що НСД 1; тобто 120 і 23 взаємно прості. Задля простоти обрані взаємно прості числа; але загальний випадок, коли НСД не дорівнює 1 спрацьовує подібним чином.

Існують два методи обробки, обидва із використанням ділення з остачею.

Ітеративний метод

Цей метод обчислює вираз виду $r_{i}=ax_{i}+by_{i}$ для остачі на кожному кроці $i$ алгоритму Евкліда. Кожний наступний номер $r_{i}$можна записати як остачу від ділення попередніх двох таких чисел, цю остачу можна виразити, використовуючи частку q_i так:

$r_{i}=r_{i-2}-q_{i}r_{i-1}.\,$

Через заміну це дає:

$r_{i}=(ax_{i-2}+by_{i-2})-q_{i}(ax_{i-1}+by_{i-1}),\,$ що можна записати як

$r_{i}=a(x_{i-2}-q_{i}x_{i-1})+b(y_{i-2}-q_{i}y_{i-1}).\,$

Перші два значення алгоритму є початковими аргументами алгоритму:

$r_{1}=a=a\times 1+b\times 0\,$

$r_{2}=b=a\times 0+b\times 1.\,$

Отже коефіцієнти мають такі початкові значення: x₁ = 1, y₁ = 0, x₂ = 0, і y₂ = 1. Інші отримуються за допомогою виразів:

$x_{i}=x_{i-2}-q_{i}x_{i-1},\,$

$y_{i}=y_{i-2}-q_{i}y_{i-1}.\,$

Вираз для останньої ненульової остачі дає бажаний результат, бо цей метод обчислює кожний залишок у вигляді a і b, як і вимагалось.

Приклад: Обчислити НСД для 120 і 23.

Обчислення відбуваються так:

Крок	Частка	Остача	Заміна	Сума термів
1		120		120 = 120 × 1 + 23 × 0
2		23		23 = 120 × 0 + 23 × 1
3	5	5 = 120 − 23 × 5	5 = (120 × 1 + 23 × 0) − (120 × 0 + 23 × 1) × 5	5 = 120 × 1 + 23 × −5
4	4	3 = 23 − 5 × 4	3 = (120 × 0 + 23 × 1) − (120 × 1 + 23 × −5) × 4	3 = 120 × −4 + 23 × 21
5	1	2 = 5 − 3 × 1	2 = (120 × 1 + 23 × −5) − (120 × −4 + 23 × 21) × 1	2 = 120 × 5 + 23 × −26
6	1	1 = 3 − 2 × 1	1 = (120 × −4 + 23 × 21) − (120 × 5 + 23 × −26) × 1	1 = 120 × −9 + 23 × 47
7	2	0	Кінець алгоритму

Розв'язок: x = −9 і y = 47.

Через те, що НСД виявився 1, отримуємо також, що 47 є оберненим до 23 за модулем 120, і також за модулем 23, -9 (або 14 = -9 + 23) є оберненим 120 (або тотожно 5 = 120 — 23 *5) .

47 × 23 ≡ 1 (mod 120) і також

−9 × 120 ≡14 × 5 ≡ 1 (mod 23).

Для того, щоб ціле a можна було обернути за модулем b, необхідно щоб a і b були взаємно простими, отже якщо НСД більший від 1, таке модульне обернення не існує.

Зауважте, що рівняння, що визначають значення x_i незалежні від тих, які визначають значення y_i, і що рівняння Безу отримане наприкінці

${\mathit {GCD}}=r_{k}=ax_{k}+by_{k}\,$

дозволяє вивести y_k коли x_k відоме. Користувач може опустити значення y_i, не обчислюючи їх (хоча вони можуть бути корисними як перевірка на помилки обчислень).

Псевдокод

РОЗШИРЕНИЙ-ЕВКЛІД$(a,b)$ якщо $b==0$  повернути $(a,1,0)$ інакше $(d',x',y')=$ РОЗШИРЕНИЙ-ЕВКЛІД$(b,a\mod b)$  $(d,x,y)=(d',y',x'-\lfloor a/b\rfloor y')$  повернути $(d,x,y)$

Якщо b не нуль, тоді РОЗШИРЕНИЙ-ЕВКЛІД спочатку обчислює (d', x', y') такі, що d' = НСД(b, a mod b) і

$d'=bx'+(a\mod {b})y'.$

Щоб отримати $x$ і $y$ такі, щоб $d=ax+by,$ ми перепишемо попереднє рівняння використавши, що $d=d'$ так:

$d$	$=bx'+(a-b\lfloor a/b\rfloor )y'$
	$=ay'+b(x'-\lfloor a/b\rfloor y').$

Швидкодія

Оскільки кількість рекурсивних викликів у звичайного і розширеного алгоритму Евкліда однакова, то їх час виконання однаковий аж до сталого множника. Тобто, для $a>b>0,$ кількість рекурсивних викликів є $O(\lg b).$

Код

C++

void ex_al_eu_in(int r1, int r2, int x1, int x2, int y1, int y2, int &gcd, int &a, int &b) {
	int r3 = r1 - r2 * (r1 / r2);
	int x3 = x1 - x2 * (r1 / r2);
	int y3 = y1 - y2 * (r1 / r2);
	if (r3)
		ex_al_eu_in(r2, r3, x2, x3, y2, y3, gcd, a, b);
	else {
		gcd = r2;
		a = x2;
		b = y2;
	}
}

void ex_al_eu(int r1, int r2, int &gcd, int &a, int &b) {
	ex_al_eu_in(r1 > r2 ? r1 : r2, r1 < r2 ? r1 : r2, 1, 0, 0, 1, gcd, r1 > r2 ? a : b, r1 < r2 ? a : b);
}

Python

def extended_euclid(a, b):
        """ Повертає d=НСД(x,y) і x, y такі, що ax + by = d """
        if (b==0):
                return a, 1, 0
        d, x, y = extended_euclid(b, a % b)
        return d, y, x - (a//b)*y

Література

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Pages 859—861 of section 31.2: Greatest common divisor.

Посилання

• How to use the algorithm by hand
• Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8) [Архівовано 25 лютого 2021 у Wayback Machine.]