Принцип алгоритму:
Розширений алгоритм Евкліда не тільки обчислює найбільший спільний дільник gcd(a, m) двох цілих чисел a та m, але також знаходить цілі числа x та y, такі що ax + my = gcd(a, m)。
Це застосування тотожності Безу (рівняння Безу).
Кроки алгоритму:
- Алгоритм Евкліда:Обчислення gcd(a, m) за допомогою ділення з остачею, записуючи частку та остачу на кожному кроці.
- Зворотна підстановка:Починаючи з останнього кроку, підставляйте назад, виражаючи кожну остачу як лінійну комбінацію a та m.
- Розв'язування коефіцієнтів:В результаті отримайте коефіцієнти x та y, що задовольняють ax + my = gcd(a, m).
Модульний обернений:
Коли gcd(a, m) = 1 (тобто a та m взаємно прості), існує мультиплікативний обернений a за модулем m, що позначається як a-1 mod m. У цьому випадку x є модульним оберненим, що задовольняє a × x ≡ 1 (mod m)。
Якщо x від'ємне, його потрібно скоригувати до додатного значення: x' = x mod m.
Застосування:
- Криптографія:Обчислення закритого ключа в алгоритмі RSA вимагає знаходження модульного оберненого.
- Задачі теорії чисел:Розв'язування лінійних конгруенцій виду ax ≡ b (mod m).
- Комбінаторика:Обчислення модульної комбінаторики (теорема Лукаса тощо)
- Спортивне програмування:Швидке обчислення модульного оберненого для уникнення проблем точності при діленні
Часова складність:
O(log min(a, m)), як і в алгоритмі Евкліда
Тотожність Безу:
Для будь-яких цілих чисел a та m існують цілі числа x та y, такі що ax + my = gcd(a, m). Ці коефіцієнти x та y можна ефективно обчислити за допомогою розширеного алгоритму Евкліда.