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

Найдите обратный элемент для взаимно простых целых чисел расширенным алгоритмом Евклида.

Расчёт обратного элемента по модулю
Введите целое число и модуль, чтобы найти наименьший неотрицательный обратный элемент.

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

Мультипликативный обратный элемент по модулю m — это целое число, которое отменяет умножение в модульной арифметике. Для целого числа a обратный элемент x удовлетворяет условию: произведение a и x при делении на m даёт остаток 1. Обычно это записывают как сравнение a, умноженного на x, с 1 по модулю m. Например, 3, умноженное на 4, равно 12, а 12 при делении на 11 даёт остаток 1, поэтому 4 — обратный элемент к 3 по модулю 11. Не для каждой пары целых чисел существует обратный элемент. Необходимое и достаточное условие — взаимная простота a и m, то есть их наибольший общий делитель равен 1. Рассмотрим 6 по модулю 9: любое кратное 6 имеет с 9 общий множитель 3 и потому не может дать остаток 1. Напротив, НОД чисел 7 и 26 равен 1, а обратный элемент к 7 по модулю 26 равен 15, поскольку 105 при делении на 26 даёт остаток 1. Перед выводом ответа калькулятор проверяет НОД. Расширенный алгоритм Евклида эффективно находит обратный элемент. Обычный алгоритм многократно выполняет деление с остатком для вычисления наибольшего общего делителя. Расширенная версия также отслеживает коэффициенты, позволяя выразить НОД целочисленной линейной комбинацией исходных чисел. Если НОД равен 1, коэффициент при a является обратным элементом. Он может быть отрицательным, поэтому калькулятор приводит его по модулю m и показывает наименьшего неотрицательного представителя от нуля до m минус один. Обратные элементы позволяют выполнять деление в системе сравнений. Чтобы решить сравнение a, умноженного на x, с b по модулю m, умножьте b на обратный элемент к a, если он существует. Обратные элементы важны для линейных сравнений, китайской теоремы об остатках, модульных дробей, хеширования, обнаружения ошибок и криптографии с открытым ключом. Например, создание ключей RSA включает поиск обратного показателя степени по модулю значения функции Эйлера. В реальных криптографических реализациях используют тщательно проверенные библиотеки произвольной точности, а не обычные числовые типы браузера. Вводите только целые числа и модуль больше 1. Значение a может быть отрицательным: каждому отрицательному целому соответствует эквивалентный наименьший неотрицательный остаток по модулю m. Калькулятор использует безопасно представимые целые числа JavaScript и подходит для учебных упражнений и задач теории чисел умеренного размера. Он показывает НОД и прямую проверку умножением, чтобы подтвердить остаток 1. Для очень больших криптографических значений используйте программы, предназначенные для больших целых чисел и вычислений с требованиями к безопасности.

Примеры обратных элементов по модулю

Каждый результат — наименьшее неотрицательное целое число, произведение с которым даёт остаток 1.

Число и модульОбратный элементПроверка
3 по модулю 114Три, умноженное на 4, равно 12, а 12 mod 11 равно 1.
7 по модулю 2615Семь, умноженное на 15, равно 105, а 105 mod 26 равно 1.
17 по модулю 31202753Семнадцать, умноженное на 2753, даёт остаток 1 по модулю 3120.
10 по модулю 1712Десять, умноженное на 12, равно 120, а 120 mod 17 равно 1.

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

  1. Введите целое число, для которого нужен мультипликативный обратный элемент.
  2. Введите целочисленный модуль больше 1.
  3. Нажмите «Найти обратный элемент», чтобы запустить расширенный алгоритм Евклида.
  4. Убедитесь, что показанное произведение даёт остаток 1 при делении на модуль.

Вопросы об обратном элементе по модулю

Когда существует мультипликативный обратный элемент по модулю?

Он существует тогда и только тогда, когда число и модуль взаимно просты. Иными словами, их наибольший общий делитель должен быть равен 1.

Почему кажется, что обратных элементов несколько?

Прибавление любого целого кратного модуля даёт сравнимого представителя. Калькулятор приводит ответ к единому виду, показывая наименьший неотрицательный обратный элемент.

Как расширенный алгоритм Евклида находит обратный элемент?

Он вычисляет НОД и одновременно отслеживает коэффициенты исходных чисел. Когда НОД равен 1, коэффициент при введённом числе является обратным элементом по модулю.

Можно ли найти обратный элемент для отрицательного числа?

Да. Отрицательное целое число можно сначала привести к эквивалентному остатку по модулю m. Калькулятор выполняет это приведение и возвращает наименьший неотрицательный обратный элемент.

Как обратные элементы используются в криптографии?

Они обращают модульное умножение в алгоритмах RSA и системах на эллиптических кривых. Для задач безопасности нужны большие целые числа и реализации с постоянным временем выполнения, выходящие за рамки этого учебного калькулятора.