Калькулятор для вычисления обратного элемента по модулю ниже, теория под ним.
Обратный элемент в кольце по модулю
Обратным к числу a по модулю m называется такое число b, что:
,
Обратный элемент обозначают как .
Для нуля обратного элемента не существует никогда, для остальных же элементов обратный элемент может как существовать, так и нет.
Утверждается, что обратный элемент существует только для тех элементов a, которые взаимно просты с модулем m.
Для нахождения обратного элемента по модулю можно использовать Расширенный алгоритм Евклида.
Для того, чтобы показать это, рассмотрим следующее уравнение:
Это линейное диофантово уравнение с двумя переменными, см. Линейные диофантовы уравнения с двумя переменными. Посколько единица может делиться только на единицу, то уравнение имеет решение только если .
Решение можно найти с помощью расширенного алгоритма Евклида. При этом, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим:
Таким образом, найденное x и будет являться обратным к a.
Обратный по модулю
❓Инструкция
Калькулятор онлайн для вычисления обратного элемента по модулю в кольце. Алгоритм поддерживает работу с большими числами с некоторыми ограничениями.
Использование:
Заполняются два поля — число a и модуль m. Число a — число к которому ищем обратный, m — модуль, по которому ищем.
Калькулятор выдает обратный элемент после нажатия на кнопку «Вычислить».
Если установлена галочка «подробнее», то калькулятор помимо обратного элемента по модулю выдает некоторые этапы вычисления.
Ограничения:
Калькулятор поддерживает работу с большими целыми числами (в том числе отрицательными числами для числа a, и только положительными для модулю m) длиной не более 10 000 символов.
📖 Теория
Что значит по модулю?
Синонимом к данному выражению является выражение «остаток от деления«. То есть выражение «5 по модулю 3» эквивалентно выражению «остаток от деления 5 на 3». И в том и в другом случае подразумевается в ответе число 2, так как остаток от деления 5 на 3 = 2.
Стоить отметить тот факт, что по модулю m мы имеем числа от 0 до m — 1. Действительно, остаток от деления на m никогда не превысит m — 1.
Что такое обратное?
Напомним, что число, умноженное на его обратное, равно 1. Из базовой арифметики мы знаем, что:
Число, обратное к числу A, равно 1 / A, поскольку A * (1 / A) = 1 (например, значение, обратное к 5, равно 1/5). Все действительные числа, кроме 0, имеют обратную Умножение числа на обратное к A эквивалентно делению на A (например, 10/5 соответствует 10 * 1/5)
Что такое обратное по модулю?
В модульной арифметике у нас нет операции деления. Тем не менее, у нас есть модульные инверсии.
Модульная инверсия a (mod m) есть a-1 (a * a-1) ≡ 1 (mod m) или эквивалентно (a * a-1) mod m = 1 Только числа, взаимно простые с модулем m, имеют модульное обратное.
Говоря проще, обратным элементом к a по модулю m является такое число b, что остаток от деления (a * b) на модуль m равно единице (a * a-1) mod m = 1
Как найти модульный обратный
Наивный метод нахождения модульного обратного a ( по модулю m) является:
Шаг 1. Рассчитать a * b mod m для значений b от 0 до m — 1
Шаг 2. Модульная инверсия a mod m — это значение b, при котором a * b mod m = 1
Обратите внимание, что термин b mod m может иметь только целочисленное значение от 0 до m — 1, поэтому тестирование больших значений чем (m-1) для b является излишним.
Вы наверно уже догадались, что наивный метод является очень медленным. Перебор всех чисел от 0 до m-1 для большого модуля довольно-таки трудоемкая задача. Существует гораздо более быстрый метод нахождения инверсии a (mod m). Таковым является расширенный алгоритм Евклида, который реализован в данном калькуляторе.
Расширенный алгоритм Евклида
Представим наибольший общий делитель числа a и модуля m в виде ax + my. То есть НОД(a, m) = ax + my. Помним, что обратный элемент существует только тогда, когда a и m взаимно просты, то есть их НОД(a, m) = 1. Отсюда: ax + my = 1 — линейное диофантово уравнение второго порядка. Необходимо решить данное уравнение в целых числах и найти x, y.
Найденный коэффициент x будет являться обратным элементом к a по модулю m. Это следует оттуда, что, если мы возьмём от обеих частей уравнения остаток по модулю m, то получим: ax = 1 (m).
Расширенный алгоритм Евклида, в отличие от классического, помимо наибольшего общего делителя позволяет найти также коэффициенты x, y.
Алгоритм:
Вход: a, m ≠ 0
Выход: d, x, y, такие что d = gcd(a, m) = ax + my
1. [Инициализация] (a0, a1) := (a, m); (x0, x1) := (1, 0); (y0; y1) := (0, 1).
2. [Основной цикл] Пока a1 ≠ 0 выполнять {q = QUO(a0, a1);
(a0, a1) := (a1, a0 — a1q); (x0, x1) := (x1, x0 — x1q); (y0, y1) := (y1, y0 — y1q);
QUO(a0, a1) — целая часть от деления a0 на a1
3. [Выход] Вернуть (d, x, y) = (a0, x0, y0)
Битовая сложность расширенного алгоритма Евклида равна O((log2(n))2) , где n = max (|a|, |m|)
Непонятен алгоритм? Ничего страшного, примеры ниже именно для этого и предназначены.
➕ Примеры
Пример для наивного метода.
Пусть a = 3, m = 7. То есть нам необходимо найти обратный элемент к 3 по модулю 7.
Шаг 1. Рассчитать a * b mod m для значений B от 0 до m-1. По очереди проверяем числа от 0 до 6.
3 * 0 ≡ 0 (mod 7) — не подходит
3 * 1 ≡ 3 (mod 7)
3 * 2 ≡ 6 (mod 7)
3 * 3 ≡ 9 ≡ 2 (mod 7)
3 * 4 ≡ 12 ≡ 5 (mod 7)
3 * 5 ≡ 15 (mod 7) ≡ 1 (mod 7) <—— Обратное найдено.
3 * 6 ≡ 18 (mod 7) ≡ 4 (mod 7)
при b = 5 выполнилось условие, что a * b ≡ 1 (m). Следовательно, b = 5 является обратным элементом к 3 по модулю 7.
Пример на расширенный алгоритм Евклида.
Пусть аналогично предыдущему примеру имеем a = 3, m = 7. Также, требуется найти обратный элемент к 3 по модулю 7. Согласно алгоритму начинаем заполнять таблицу на каждом этапе цикла.
| Итерация | q | a0 | a1 | x0 | x1 | y0 | y1 |
| 0 | — | 3 | 7 | 1 | 0 | 0 | 1 |
| 1 | 0 | 7 | 3 | 0 | 1 | 1 | 0 |
| 2 | 2 | 3 | 1 | 1 | -2 | 0 | 1 |
| 3 | 3 | 1 | 0 | -2 | 0 | 1 | -3 |
После 3-ей итерации получили a1 = 0, строго по алгоритму из раздела «Теория» заканчиваем работу алгоритма.
(d, x, y) = (a0, x0, y0)
(d, x, y) = (1, -2, 1), видим, что d = НОД(3, 7) = 1, следовательно числа 3 и 7 являются взаимно простыми, а значит обратный существует.
Делаем проверку:
3 * (-2) + 7 * 1 = 1
-6 + 7 = 1
1 = 1 — верно!
Обратным элементом к тройке по модулю 7 является x = -2. По модулю 7 число -2 равно 5. Получили, что x = 5 является обратным элементом к 3 по модулю 7.
Есть два пути для решения этой задачи.
Путь первый — использование расширенного алгоритма Евклида.
Алгоритм Евклида ищет НОД двух чисел. Расширенный алгоритм Евклида одновременно с этим представляет НОД как целочисленную линейную комбинацию исходных чисел:
Ka∙a + Kb∙b = (a, b)
Как легко заметить, если A и C не являются взаимно простыми, то решения нет, а если являются — то коэффициент при A и будет искомым обратным элементом (для доказательства можно заменить в формуле выше b на C и взять обе части равенства по модулю C).
Рекурсивный алгоритм довольно прост. На очередном шаге большее из двух чисел (для определенности, a) представляется как c + k∙b, после чего алгоритм вызывается рекурсивно для (b, c):
Ka∙(c + k∙b) + Kb∙b = (a, b)
Ka∙c + (Kb + Ka∙k)∙b = (c + k∙b, b) = (c, b)
Kc1∙c + Kb1∙b = (c, b)
Отсюда имеем Ka = Kc1 и Kb = Kb1 — Kc1∙k
Получаем примерно такой алгоритм:
ФУНКЦИЯ НОД(a, b) -> (d, Ka, Kb):
ЕСЛИ (b == 0) ВЕРНУТЬ (a, 1, 0)
(d, Kb1, Kc1) = НОД(b, a % b);
ВЕРНУТЬ (d, Kc1, Kb1 - ⌊a/b⌋ ∙ Kc1);
Итеративный алгоритм столь же прост в реализации, но сложнее в понимании. Проще всего использовать матрицы. Для начала, следует записать преобразование коэффициентов в матричном виде:
| 0 1 |
(Ka Kb) = (Kb1, Kc1) | |
| 1 -⌊a/b⌋ |
Эти матричные множители можно будет накопить:
|K11 K12| | 0 1 | |K11` K12`|
| | = | | | |
|K21 K22| | 1 -⌊a/b⌋ | |K21` K22`|
Получается следующий алгоритм:
ФУНКЦИЯ НОД(a, b) -> (d, Ka, Kb):
K = (1, 0)(0, 1) // Начинаем с единичной матрицы
ПОКА b > 0
K = (K[1, 0], K[1, 1])(K[0, 0] - ⌊a/b⌋∙K[1, 0], K[0, 1] - ⌊a/b⌋∙K[1, 1])
(a, b) = (b, a % b)
ВЕРНУТЬ (a, (K[0, 0], K[0, 1])
Теперь, когда у нас есть НОД, осталось найти НОД(A, C), проверить что он равен 1 и взять (Ka % C) в качестве искомого обратного числа.
Время работы — порядка log A по основанию φ итераций (это связано с тем, что худший случай для алгоритма Евклида — соседние числа Фибоначчи).
Путь второй — использование формулы Эйлера
Если число C заранее известно, или есть достаточно времени на подготовку, то можно воспользоваться формулой Эйлера:
A ^ φ(C) = 1 (mod C) для взаимно простых A и C
Поскольку для имеющих нетривиальные общие делители A и C задача решения все равно не имеет — ограничение нам не помешает.
В соответствии с формулой, ответом будет A ^ (φ(C) - 1) % C. Быстро найти его можно при помощи алгоритма быстрого возведения в степень:
ФУНКЦИЯ СТЕПЕНЬ (a, x, c):
b = 1
ПОКА x > 0:
ЕСЛИ x - НЕЧЕТНОЕ, ТО
x = x - 1
b = (b * a) % c
ИНАЧЕ
x = x / 2
a = (a * a) % c
ВЕРНУТЬ b
Корректность этого алгоритма легко доказывается если заметить что a ^ x * b — его инвариант.
Разумеется, после получения ответа надо будет проверить что он правильный, если он будет неверным — значит, ответа вовсе не существует (A и C имеют общие делители).
Этот алгоритм будет работать быстрее чем алгоритм Евклида, потому что тут основание логарифма больше, а сами итерации — проще. Но для применения этого алгоритма требуется заранее знать φ(C)
Обратный элемент в кольце по модулю
Нахождение с помощью Бинарного возведения в степень
Нахождение с помощью Бинарного возведения в степень
Воспользуемся теоремой Эйлера:
которая верна как раз для случая взаимно простых
и .
Кстати говоря, в случае простого модуля
мы получаем ещё более простое утверждение — малую теорему Ферма:
Умножим обе части каждого из уравнений на , получим:
- для любого модуля
- :
- для простого модуля
- :
Таким образом, мы получили формулы для непосредственного вычисления обратного.
[ http://e-maxx.ru/algo/reverse_element ]
Обратный элемент в кольце по модулю
и его часто еще обозначают a-1.
Для нуля такого обратного элемента вовсе не бывает, а для всех остальных — обратный элемент может существовать только для тех элементов a, которые взаимно просты с модулем m.
Есть 2 способа, чтобы найти обратный элемент: это бинарное возведение в степень и с помощью расширенного алгоритма Евклида. В данном случае используется второй вариант.
Кому интересно больше узнать о данном способе, то вы можете сделать это просто зайдя на данную страницу: