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

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