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

Розширений алгоритм Евкліда — це розширення алгоритму Евкліда. Окрім знаходження найбільшого спільного дільника для цілих 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 спрацьовує подібним чином.

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

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

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

$r_i=r_{i-2}-q_i{r}_{i-1}.$

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

$r_i=(a{x}_{i-2}+b{y}_{i-2})-q_i(a{x}_{i-1}+b{y}_{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.$

Отже коефіцієнти мають такі початкові значення: Шаблон:Nowrap, Шаблон:Nowrap, Шаблон:Nowrap, і Шаблон:Nowrap. Інші отримуються за допомогою виразів:

$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, і що рівняння Безу отримане наприкінці

$𝐺𝐶𝐷=r_k=a{x}_k+b{y}_k$

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

Псевдокод

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

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

$d^{\prime }=b{x}^{\prime }+(amodb)y^{\prime }.$

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

$d$	$=b{x}^{\prime }+(a-b\lfloor a/b\rfloor )y^{\prime }$
	$=a{y}^{\prime }+b(x^{\prime }-\lfloor a/b\rfloor y^{\prime }).$

Швидкодія

Оскільки кількість рекурсивних викликів у звичайного і розширеного алгоритму Евкліда однакова, то їх час виконання однаковий аж до сталого множника. Тобто, для $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) Шаблон:Webarchive