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

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

1. Введите число \(a\) в поле Число (a) — значение, для которого нужен обратный элемент.
2. Введите модуль в поле Модуль (n). Он должен быть больше 1.
3. Прочитайте результат Обратный элемент — значение \(x\), для которого \(a \cdot x \equiv 1 \pmod{n}\).
4. Проверьте строку Проверка, в которой показана верификация \(a \times x \equiv 1 \bmod n\).

Если \(a\) и \(n\) имеют общий делитель больше 1, калькулятор сообщит, что обратный элемент не существует, поскольку никакое кратное \(a\) не может быть сравнимо с 1 по модулю \(n\).

Что такое обратный элемент по модулю?

В обычной арифметике обратным числом является обратная величина: обратное к 3 — это \(1/3\), поскольку \(3 \cdot 1/3 = 1\). В модулярной арифметике дробей нет, поэтому обратный элемент определяется иначе. Обратным элементом числа \(a\) по модулю \(n\) называется целое число \(x\), такое что

\[ a \cdot x \equiv 1 \pmod{n} \]

Иными словами, если умножить \(a\) на \(x\) и разделить на \(n\), остаток будет равен ровно 1. Например, \(3 \times 4 = 12\), а 12 при делении на 11 даёт остаток 1, поэтому 4 — обратный элемент числа 3 по модулю 11. У каждого числа, взаимно простого с модулем, есть ровно один обратный элемент в диапазоне от \(0\) до \(n-1\).

Это понятие важно, потому что модулярное «деление» — это на самом деле умножение на обратный элемент. Чтобы решить \(a \cdot x \equiv b \pmod{n}\), нужно умножить обе части на обратный элемент числа \(a\) — тот же приём, что и деление обеих частей обычного уравнения, но выполняемый так, чтобы оставаться в целых числах.

Обратные элементы по модулю также играют центральную роль в криптографии. При генерации ключей RSA частная экспонента вычисляется как обратный элемент открытой экспоненты по модулю \(\varphi(n)\); схемы Диффи–Хеллмана и эллиптических кривых опираются на обратные элементы в конечных полях. Помимо криптографии, обратные элементы встречаются в кодах с коррекцией ошибок, хешировании и теоретико-числовых задачах, решаемых с помощью таких инструментов, как китайская теорема об остатках.

Когда обратный элемент существует (а когда нет)

Обратный элемент числа \(a\) по модулю \(n\) существует тогда и только тогда, когда \(\gcd(a, n) = 1\). Числа с НОД, равным 1, называются взаимно простыми. Причина видна из тождества расширенного алгоритма Евклида: оно может дать \(a \cdot x + n \cdot y = 1\) только тогда, когда 1 представимо в виде комбинации \(a\) и \(n\), что происходит ровно тогда, когда их НОД равен 1.

Например, у числа 6 нет обратного элемента по модулю 9, потому что \(\gcd(6, 9) = 3\): каждое кратное 6 делится на 3 и потому никогда не может давать остаток 1. Но у 6 есть обратный элемент по модулю 11, так как \(\gcd(6, 11) = 1\).

Полезное упрощение: если модуль \(n\) — простое число, то у каждого \(a\) от 1 до \(n-1\) есть обратный элемент, поскольку ни одно число, меньшее простого, не имеет с ним общих делителей. В этом особом случае обратный элемент можно также вычислить с помощью малой теоремы Ферма как \(a^{n-2} \bmod n\); для составных модулей аналогичный результат \(a^{\varphi(n)-1}\) даёт теорема Эйлера

Ограничения и практические замечания

• Калькулятор требует \(n > 1\); по модулю 1 каждое число сравнимо с 0, и обратный элемент не имеет смысла.
• Введите положительное \(a\). Если нужен обратный элемент отрицательного числа, сначала приведите его: обратный элемент для \(-a\) равен обратному элементу для \(n - a\).
• Результат всегда возвращается в диапазоне \(0 \le x < n\) — это стандартный представитель решения.
• Для очень больших чисел (сотни цифр, как в реальной криптографической работе) вычисления в браузере достигают предела; этот калькулятор предназначен для повседневного и учебного использования.
• Расширенный алгоритм Евклида работает за логарифмическое время, поэтому даже большие «ручные» входные данные обрабатываются мгновенно — нет необходимости перебирать значения-кандидаты одно за другим.