Принцип алгоритма:
Расширенный алгоритм Евклида не только вычисляет наибольший общий делитель 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)), как и у алгоритма Евклида