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

Материал из Algocode wiki
Версия от 11:20, 30 августа 2019; Romanchenko (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Нахождение обратного элемента в кольце вычетов

Простой модуль

Начнем с базового случая - когда модуль простой. Рассмотрим два способа:

  1. С помощью МТФ. Заметим, что если $p$ - простой модуль, то $a^{p-1}\equiv 1 \mod p$, если $a$ не делится на $p$. Тогда для $a$ обратным элементом будет $a^{p-2}$.
  2. С помощью расширенного алгоритма Евклида. Пусть $x$ - искомый обратный элемент. Тогда $ax = 1 - yp$, где $y$ - какое-то целое число. Перепишем это равенство: $ax + yp = 1$. Если $a$ имеет с $p$ общий делитель, отличный от единицы, то оно делится на $p$, этот случай отсеивается проверкой. Теперь считаем, что $(a, p) = 1$. Расширенный алгоритм Евклида, примененный к паре $a, p$, как раз находит такие $x, y$, что $ax + yp = (a, p) = 1$. Тогда решение сводится к запуску расширенного алгоритма Евклида и возвращению одного из найденных коэффициентов.

Составной модуль

TODO.



Автор конспекта: Полина Романченко

По всем вопросам пишите в telegram @Romanchenko