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

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

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

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

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

ред.

Цей метод обчислює вираз виду   для остачі на кожному кроці   алгоритму Евкліда. Кожний наступний номер  можна записати як остачу від ділення попередніх двох таких чисел, цю остачу можна виразити, використовуючи частку qi так:

 

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

  що можна записати як
 

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

 
 

Отже коефіцієнти мають такі початкові значення: x1 = 1, y1 = 0, x2 = 0, і y2 = 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, і що рівняння Безу отримане наприкінці

 

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

Псевдокод

ред.

РОЗШИРЕНИЙ-ЕВКЛІД 

  1. якщо  
  2. повернути  
  3. інакше   РОЗШИРЕНИЙ-ЕВКЛІД 
  4.  
  5. повернути  

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

 

Щоб отримати   і   такі, щоб   ми перепишемо попереднє рівняння використавши, що   так:

   
 

Швидкодія

ред.

Оскільки кількість рекурсивних викликів у звичайного і розширеного алгоритму Евкліда однакова, то їх час виконання однаковий аж до сталого множника. Тобто, для   кількість рекурсивних викликів є  

Код

ред.
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);
}
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.

Посилання

ред.