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

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

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

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

ДіленеДільникЧасткаОстача
1202355
23543
5312
3211
2120

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

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

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

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

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

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

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

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

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

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

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

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

КрокЧасткаОстачаЗамінаСума термів
1120120 = 120 × 1 + 23 × 0
22323 = 120 × 0 + 23 × 1
355 = 120 − 23 × 55 = (120 × 1 + 23 × 0) − (120 × 0 + 23 × 1) × 55 = 120 × 1 + 23 × −5
443 = 23 − 5 × 43 = (120 × 0 + 23 × 1) − (120 × 1 + 23 × −5) × 43 = 120 × −4 + 23 × 21
512 = 5 − 3 × 12 = (120 × 1 + 23 × −5) − (120 × −4 + 23 × 21) × 12 = 120 × 5 + 23 × −26
611 = 3 − 2 × 11 = (120 × −4 + 23 × 21) − (120 × 5 + 23 × −26) × 11 = 120 × −9 + 23 × 47
720 Кінець алгоритму

Розв'язок: 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. повернути

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

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.