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

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

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

Якщо 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 egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, 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.

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


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.