Розширений алгоритм Евкліда —це розширення алгоритму Евкліда. Окрім знаходження найбільшого спільного дільника для цілих a і b, як це робить алгоритм Евкліда, він також знаходить цілі x і y (одне з яких зазвичай від'ємне), які задовольняють рівнянню Безу.
Розширений алгоритм Евкліда особливо корисний коли a і b взаємно прості числа, бо x — обернене щодо a за модулем b, а y — обернене щодо b за модулем a.
Неформальне визначення алгоритму Редагувати
Для пояснення алгоритму Евкліда, розглянемо обчислення НСД(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) .
−9 × 120 ≡14 × 5 ≡ 1 (mod 23).
Для того, щоб ціле a можна було обернути за модулем b, необхідно щоб a і b були взаємно простими, отже якщо НСД більший від 1, таке модульне обернення не існує.
Зауважте, що рівняння, що визначають значення xi незалежні від тих, які визначають значення yi, і що рівняння Безу отримане наприкінці
дозволяє вивести yk коли xk відоме. Користувач може опустити значення yi, не обчислюючи їх (хоча вони можуть бути корисними як перевірка на помилки обчислень).
Псевдокод Редагувати
| РОЗШИРЕНИЙ-ЕВКЛІД
|
Якщо 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.
Посилання Редагувати
- Source for the form of the algorithm used to determine the multiplicative inverse in GF(2^8) [ 25 лютого 2021 у Wayback Machine.]
| Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її. |