Как найти обратное по модулю: расширенный алгоритм Евклида

Дано: число $a = 37$ и модуль $n = 120$. Найти: такое целое $x$, что $37x \equiv 1 \pmod{120}$.

Обратный элемент по модулю существует ровно тогда, когда число и модуль взаимно просты, а вычисляется расширенным алгоритмом Евклида. Здесь $\gcd(37, 120) = 1$, поэтому обратный есть и среди вычетов от 0 до 119 он единственный: ответ равен 13, то есть $37^{-1} \equiv 13 \pmod{120}$. Проверка укладывается в одну строку: $37 \cdot 13 = 481 = 4 \cdot 120 + 1$. Калькулятор сверху проделывает то же самое для любой пары «число и модуль», ниже - решение по шагам.

Решение по шагам

Дано. $a = 37$, $n = 120$.

Найти. Целое $x$ из промежутка от 0 до 119, для которого $37x \equiv 1 \pmod{120}$.

Шаг 1. Проверяем, существует ли обратный вообще. Прежде чем что-то считать, нужно убедиться, что число и модуль взаимно просты. Прогоняем деления с остатком:

$$120 = 3 \cdot 37 + 9, \qquad 37 = 4 \cdot 9 + 1, \qquad 9 = 9 \cdot 1 + 0.$$

Последний ненулевой остаток равен единице, значит $\gcd(37, 120) = 1$ и обратный элемент существует. Сама лестница делений разобрана подробно в задаче про НОД двух чисел, здесь она нужна только как заготовка: те же три строки сейчас дадут и ответ.

Шаг 2. Дописываем к лестнице столбец коэффициентов. Идея расширенного алгоритма в том, чтобы рядом с каждым остатком вести число $t$, для которого выполнено $r \equiv t \cdot 37 \pmod{120}$. Начальные значения очевидны: остаток 120 это нуль по модулю 120, поэтому у него $t = 0$; у остатка 37 коэффициент $t = 1$. Дальше каждый новый коэффициент считается по той же формуле, что и остаток, с тем же неполным частным.

Каждая строка таблицы проверяется независимо, и это удобно на контрольной: остаток 9 должен быть сравним с $-3 \cdot 37 = -111$, а $-111 + 120 = 9$ - сходится.

Шаг 3. Читаем ответ из строки с остатком 1. Нужная строка - вторая: остаток там равен единице, а коэффициент равен 13. Разворачивая сравнение обратно в равенство целых чисел, получаем соотношение Безу:

$$1 = 13 \cdot 37 - 4 \cdot 120.$$

Слагаемое с модулем при переходе к сравнению по модулю 120 исчезает, и остаётся ровно то, что требовалось: $13 \cdot 37 \equiv 1 \pmod{120}$.

Шаг 4. Приводим коэффициент к стандартному представителю. Расширенный алгоритм часто выдаёт отрицательное число, и это не ошибка: достаточно прибавить модуль. Здесь коэффициент 13 уже лежит в промежутке от 0 до 119, поэтому шаг холостой. А вот для пары $a = 7$, $n = 26$ алгоритм выдаёт $-11$, и ответом служит $-11 + 26 = 15$.

Шаг 5. Проверяем умножением. Обратный элемент обязан давать остаток 1, и проверка стоит одного умножения с делением:

$$37 \cdot 13 = 481, \qquad 481 = 4 \cdot 120 + 1.$$

Ответ. $37^{-1} \equiv 13 \pmod{120}$.

Почему обратный элемент есть не у каждого числа

Условие взаимной простоты не формальность, а ровно граница между разрешимой и неразрешимой задачей. Пусть обратный существует, то есть $ax \equiv 1 \pmod n$. По определению сравнения это значит, что разность $ax - 1$ делится на $n$, то есть найдётся целое $k$ с равенством $ax - kn = 1$. Любой общий делитель $d$ чисел $a$ и $n$ делит левую часть, а значит делит и единицу. Единственный положительный делитель единицы - она сама, поэтому $\gcd(a, n) = 1$.

Обратное утверждение даёт соотношение Безу: если наибольший общий делитель равен единице, то найдутся целые $x$ и $y$ с $ax + ny = 1$, и этот самый $x$ и есть обратный элемент. Расширенный алгоритм Евклида как раз и предъявляет пару коэффициентов явно, поэтому доказательство существования и способ вычисления здесь - одно и то же действие.

Полезно посмотреть на ту же мысль глазами. Возьмём число 38 вместо 37 при том же модуле: $\gcd(38, 120) = 2$. Любое произведение $38k$ чётно, остаток чётного числа при делении на чётный модуль 120 тоже чётен, а единица нечётна - совпасть неоткуда. На графике «орбита остатков» в калькуляторе сверху это видно сразу: точки садятся только на чётные уровни, а горизонталь единицы пустует. Для взаимно простой пары картинка другая: остатки пробегают все вычеты ровно по одному разу, и ровно одна точка попадает на единицу.

Сколько вообще обратимых вычетов по данному модулю, считает функция Эйлера. Для $n = 120 = 2^3 \cdot 3 \cdot 5$ получаем

$$\varphi(120) = 120 \cdot \left(1 - \tfrac{1}{2}\right)\left(1 - \tfrac{1}{3}\right)\left(1 - \tfrac{1}{5}\right) = 32,$$

то есть из 120 вычетов обратимы только 32 - их показывает второй режим графика. Особый случай - простой модуль: тогда с модулем взаимно просты все ненулевые вычеты, обратим каждый из них, и арифметика по такому модулю ведёт себя как обычные дроби. Именно поэтому в криптографии модуль почти всегда либо простой, либо произведение двух простых, а проверка числа на простоту идёт первым шагом всех построений.

Второй способ: через функцию Эйлера

Есть формула, которая даёт обратный элемент без всякого алгоритма Евклида. Теорема Эйлера утверждает, что при $\gcd(a, n) = 1$ выполнено $a^{\varphi(n)} \equiv 1 \pmod n$. Разделив показатель на одну единицу, получаем готовое выражение:

$$a^{-1} \equiv a^{\varphi(n) - 1} \pmod n.$$

Для нашей задачи $\varphi(120) = 32$, поэтому $37^{-1} \equiv 37^{31} \pmod{120}$. Считать такую степень в лоб не нужно, работает быстрое возведение в степень по модулю. Здесь выкладка и вовсе короткая: $37^2 = 1369 = 11 \cdot 120 + 49$, то есть $37^2 \equiv 49$, а $49^2 = 2401 = 20 \cdot 120 + 1$, то есть $37^4 \equiv 1$. Тогда $37^{31} = (37^4)^7 \cdot 37^3 \equiv 37^3 \equiv 37 \cdot 49 = 1813 = 15 \cdot 120 + 13$, снова 13.

Для простого модуля $p$ функция Эйлера равна $p - 1$, и формула превращается в малую теорему Ферма: $a^{-1} \equiv a^{p-2} \pmod p$. Например, обратный к 5 по модулю 13 равен $5^{11} \bmod 13 = 8$, и проверка сходится: $5 \cdot 8 = 40 = 3 \cdot 13 + 1$.

У способа есть цена. Он требует знать $\varphi(n)$, а это по сути разложение модуля на простые множители - задача несопоставимо более дорогая, чем несколько делений с остатком. Расширенный алгоритм Евклида работает за число шагов порядка логарифма от модуля и никакого разложения не требует, поэтому в программах обратный элемент ищут именно им. Формула Эйлера удобна в теории и в устном счёте для маленьких простых модулей.

Подбор множителя для маленьких модулей

Когда модуль двузначный или трёхзначный, ответ можно получить вообще без техники. Сравнение $37x \equiv 1 \pmod{120}$ равносильно равенству $37x = 1 + 120t$ с целым $t$, откуда $x = (1 + 120t) / 37$. Перебираем $t$ начиная с нуля и смотрим, когда числитель разделится нацело: 1, 121, 241, 361 не делятся на 37, а $481 : 37 = 13$ - готово. Четыре пробы, никаких таблиц.

Приём ценен ещё и как страховка. Если расширенный алгоритм дал ответ, его всё равно проверяют умножением, а перебор по $t$ сразу даёт и обратный элемент, и то самое неполное частное 4 из проверки. Но растёт он линейно по модулю: для четырёхзначных чисел перебор уже безнадёжен, а для модулей из криптографии бессмысленен в принципе.

Отдельно стоит помнить про приведение исходного числа. Если $a$ больше модуля или отрицательно, сначала берут остаток: обратный к 157 по модулю 120 - это обратный к 37, потому что $157 = 120 + 37$, и ответ тот же самый. Это бесплатно уменьшает числа и снижает шанс арифметической ошибки.

Частые ошибки

• Ищут обратный, не проверив НОД. Если $\gcd(a, n) > 1$, обратного нет вовсе, и расширенный алгоритм выдаст не единицу, а этот самый НОД. Строка «остаток 1» в таблице просто не появится.
• Забывают привести отрицательный коэффициент. Коэффициент $-11$ по модулю 26 - верный, но не канонический ответ: в ответ пишут $-11 + 26 = 15$. Прибавлять модуль нужно столько раз, сколько потребуется, чтобы попасть в промежуток от 0 до $n - 1$.
• Путают коэффициенты при числе и при модуле. В соотношении $1 = 13 \cdot 37 - 4 \cdot 120$ обратным служит множитель при 37, то есть 13, а не $-4$. Множитель при модуле в сравнении исчезает и в ответе не участвует.
• Считают, что простого числа достаточно. Важна взаимная простота с модулем, а не простота самого числа: у 5 по модулю 120 обратного нет, хотя 5 простое, ведь $\gcd(5, 120) = 5$.
• Берут обратное по неверному модулю в RSA. Закрытая экспонента ищется как обратный элемент к открытой по модулю значения функции Эйлера, а не по модулю произведения простых. Подробный разбор с числами - в задаче про генерацию ключей RSA.
• Пытаются делить. Запись $a^{-1}$ не означает дробь $1/a$: в целых числах по модулю деления нет, есть только умножение на обратный элемент, и существует он далеко не всегда.

FAQ

Чем обратный элемент по модулю отличается от дроби? Дробь $1/37$ - рациональное число, а обратный элемент - целое число из промежутка от 0 до $n - 1$, произведение с которым даёт остаток 1. По модулю 120 роль «одной тридцать седьмой» играет 13, по модулю 121 у того же числа 37 обратный уже другой. Ответ всегда привязан к модулю, без него вопрос смысла не имеет.

Сколько обратных элементов у числа по данному модулю? Формально бесконечно много, но все они отличаются на кратное модуля и образуют один класс вычетов: 13, 133, 253 и так далее, а также $-107$. В ответ пишут наименьшего неотрицательного представителя класса, то есть 13. Внутри промежутка от 0 до $n - 1$ обратный ровно один.

Что делать, если число больше модуля или отрицательное? Сначала привести его по модулю, взяв остаток. Для $a = -83$ и $n = 120$ остаток равен 37, значит обратный тот же самый - 13. Расширенный алгоритм отработает и без приведения, но с меньшими числами ошибиться труднее.

Зачем обратный элемент нужен на практике? На нём держится асимметричная криптография: закрытый ключ RSA - это обратный элемент к открытой экспоненте по модулю функции Эйлера. Кроме того, через обратный элемент решают линейные сравнения и делят в полях вычетов, где обычного деления нет.

Коротко

1. Проверяем взаимную простоту: $\gcd(37, 120) = 1$, значит обратный элемент существует и единственный среди вычетов от 0 до 119.
2. Прогоняем расширенный алгоритм Евклида, ведя рядом с остатками столбец коэффициентов при 37: $120 = 3 \cdot 37 + 9$ даёт $t = -3$, затем $37 = 4 \cdot 9 + 1$ даёт $t = 13$.
3. Строка с остатком 1 и содержит ответ: $1 = 13 \cdot 37 - 4 \cdot 120$, то есть $37^{-1} \equiv 13 \pmod{120}$.
4. Отрицательный коэффициент приводим прибавлением модуля, положительный оставляем как есть. Проверка обязательна: $37 \cdot 13 = 481 = 4 \cdot 120 + 1$.
5. Альтернативы: формула $a^{\varphi(n) - 1}$ при известной функции Эйлера и перебор $t$ в равенстве $37x = 1 + 120t$, дающий $t = 4$ и $x = 13$.