Обратный элемент в кольце по модулю
Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.
Обратный элемент в кольце по модулю
Рассчитать
Обратный элемент
Ссылка Сохранить Виджет
Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .
Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.
Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.
Для того, чтобы показать это, рассмотрим следующее уравнение:
Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:
Таким образом, найденное x и будет являться обратным к a.
RSA с нуля
при этом числа и должны быть взаимно простыми. Это значит, что не делится на . Соответственно единственный их общий делитель (он же наибольший) — это 1.
Для расчета обратного числа по модулю применяется расширенный алгоритм Евклида и соотношение Безу.
Соотношение Безу говорит, что существуют такие целые числа , , которые удовлетворяют следующему выражению:
Для нашего случая:
Если взять левую и правую часть по модулю , то
Чтобы найти наше обратное, нам нужно вычислить коэффициент в соотношении Безу.
Иногда получается отрицательным, можем взять его положительный модуль по без ущерба для исходного уравнения.
Обратное число к а по модулю m
Обратное число Даны два целых числа m и a. Если не существует обратного числа к a по модулю m, то выведите число −1, а если существует, то выведите это число (ответ должен лежать в границах от 0 до m−1). Входные данные В единственной строке входных данных даны два целых числа 1 Выходные данные Выведите ответ на задачу. Примеры Ввод 179 57 Вывод 22
b = 0 a = list(map(int, input().split())) b = pow(a[1], a[0] - 2, a[0]) if pow(a[1], a[0] - 2, a[0]) == 0: print(-1) else: print(b) Отслеживать
30.3k 3 3 золотых знака 18 18 серебряных знаков 55 55 бронзовых знаков
Обратный по модулю
Фактическая польза от обратного по модулю в том, что он заменяет деление. А именно, если нам в рамках вычислений хочется найти значение $\frac \pmod
$, то мы считаем это значение эквивалентным значению $A \cdot B^ \pmod
$.
Чтобы найти обратное по модулю, есть несколько разных техник, но самая популярная — теорема Эйлера:
Теорема Эйлера
Или это же выражение для простого модуля $p$ называется малой теоремой Ферма:
Малую теорему Ферма можно достаточно просто доказать комбинаторно. Поставим другую задачу — подсчет числа способов раскрасить $p$-угольник в $a$ цветов. Раскрасим каждую вершину в какой-то цвет. Всего таких раскрасок $a^p$. Заметим, что поскольку $p$ простое, то у всех раскрасок, кроме тех, где все раскрашено в один цвет поворотом получается ровно $p$ раскрасок. Значит всего различных раскрасок $\frac
+ a$. Это число должно быть целым, а значит $a^p — a$ делится на $p$, откуда $a^
— 1 \equiv 0 \pmod
$.
Как теперь научиться делить? Все просто:
Значит, для простых $p$ достаточно посчитать $a^$ с помощью быстрого возведения в степень
Диофантово уравнение
Альтернативный вариант — свести уравнение $ax \equiv 1 \pmod
$ к диофантову уравнению $$ ax + py = 1$$