Калькулятор обратного элемента по модулю

Введите расчет

Целое число a

Модуль m

Результатов

Modular inverse a^-1 (mod m)

3

the integer x with a·x ≡ 1 (mod m)

НОД(a, m)	1
Диапазон вычета	0 ≤ x < m

Что такое калькулятор обратного элемента по модулю?

Этот калькулятор находит мультипликативный обратный элемент целого числа a по модулю m — единственное целое x в диапазоне 0 ≤ x < m, для которого выполняется \(a\cdot x \equiv 1 \pmod{m}\). В основе лежит расширенный алгоритм Евклида, который попутно возвращает наибольший общий делитель НОД(a, m). Это чистая теория чисел, поэтому результат одинаков в любой стране и не зависит от каких-либо национальных правил. Обратный элемент по модулю широко применяется в криптографии (например, при генерации ключей RSA), в хеш-функциях и при решении линейных сравнений.

Как пользоваться

Введите целое число a и положительный модуль m (берите m ≥ 2, чтобы обратный элемент был осмысленным и единственным). Инструмент приводит a по модулю m, запускает расширенный алгоритм Евклида и выдаёт обратный элемент вместе с НОД(a, m). Если a и m не взаимно просты (НОД ≠ 1), обратного элемента не существует — калькулятор сообщит об этом.

Разбор формулы

Обратный элемент существует тогда и только тогда, когда НОД(a, m) = 1. Расширенный алгоритм Евклида находит такие целые числа s и t, что \(a\cdot s + m\cdot t = \text{НОД}(a, m)\). Когда НОД равен 1, получаем \(a\cdot s \equiv 1 \pmod{m}\), поэтому обратный элемент равен

$$x = ((s \bmod m) + m) \bmod m$$

— приведённый к наименьшему неотрицательному вычету.

Реклама

Обратное x — это значение, при котором a*x оборачивается по модулю и равно 1.

Разбор примера

Возьмём a = 7, m = 4. Поскольку \(7 \equiv 3 \pmod{4}\), решаем \(3x \equiv 1 \pmod{4}\). Расширенный алгоритм Евклида для пары (7, 4) даёт НОД = 1 и коэффициент Безу s = -1, поэтому

$$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$

Проверка: \(7\cdot 3 = 21 = 5\cdot 4 + 1 \equiv 1 \pmod{4}\). Ответ — 3.

Расширенный алгоритм Евклида находит обратное и gcd(a, m) за один проход.

Частые вопросы

Когда обратный элемент не существует? Только если НОД(a, m) > 1. Например, для a = 6, m = 9 НОД = 3, поэтому обратного элемента нет.

Может ли a быть отрицательным или больше m? Да. Мы сначала приводим a по модулю m; результат от этого не меняется, ведь \(a \equiv a' \pmod{m}\).

Что если m = 1? По модулю 1 любое целое число сравнимо с 0, поэтому обратный элемент тривиально равен 0.