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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Розширений алгоритм Евкліда —це розширення алгоритму Евкліда. Окрім знаходження найбільшого спільного дільника для цілих 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 = a x_i + b y_i для остачі на кожному кроці i алгоритму Евкліда. Кожний наступний номер r_iможна записати як остачу від ділення попередніх двох таких чисел, цю остачу можна виразити, використовуючи частку qi так:

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\times1 + b\times0\,
r_2 = b = a\times0 + b\times1.\,

Отже коефіцієнту стартують як x1 = 1, y1 = 0, x2 = 0, і y2 = 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, таке модульне обернення не існує.

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

 \mathit{GCD} = r_k = a x_k + b y_k\,

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

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

Пояснення[ред.ред. код]

Якщо b=0, то НСД дорівнює a, і коефіцієнт біля a — одиниця, біля b — нуль. Інакше алгоритм рекурсивно викликає себе для b і a mod b, отримуючи в результаті d=bx'+(a mod b)y'. Лема Безу говорить про те, що d все одно можна представити у вигляді d = ax+by, і до такого виду рівняння приводиться нижче:

d=bx'+(a-(a div b)*b)y';
d=ay'+b(x'-(a div b)y');

Звідси, коефіцієнт біля x = y' (коефіцієнт біля a), y = x' — (a div 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.

Посилання[ред.ред. код]