Вычисление мультипликативных обратных элементов по заданному модулю

Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-кольце $Z_p$.

Теорема.

Пусть $\bar a \in Z_p$, тогда класс $a$ имеет мультипликативный обратный элемент по модулю $p$ тогда и только тогда, когда $(a_1, p) = 1$.

Теорема.

Характеристика $\lambda$ конечного поля – простое число.

Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.

Первый способ

Из условия $(a, p) = 1$ получаем $a \cdot x + p \cdot y = 1$ или $a \cdot x \equiv 1 \pmod{p}$ и, следовательно, $x$ – мультипликативный обратный к $a$ по модулю $p$.

Второй способ

Напомним теорему Эйлера.

Определение

Функция Эйлера $\varphi (n)$ — это количество чисел от $1$ до $n$, взаимно простых с $n$.

Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с $n$ равен единице.

Tеоремa Эйлера

Если $a$ и $p$ взаимно просты, то $a^{\varphi(p)} \equiv 1 \pmod p$, где $\varphi (n)$ - функция Эйлера.

Доказательство теоремы достаточно простое, возможны различные варианты. Приведем здесь теоретико-числовое доказательство.

Доказательство.

Пусть $x_1, \dots, x_{\varphi(p)}$ — все различные натуральные числа, меньшие $p$ и взаимно простые с ним.

Рассмотрим все возможные произведения $x_i a$ для всех $i$ от $1$ до $\varphi(p)$.

Поскольку $a$ взаимно просто с $p$ и $x_i$ взаимно просто с $p$, то и $x_i a$ также взаимно просто с $p$, то есть $x_i a \equiv x_j\pmod p$ для некоторого $j$.

Отметим, что все остатки $x_i a$ при делении на $p$ различны. Действительно, пусть это не так, то существуют такие $i_1 \neq i_2$, что

$x_{i_1} a \equiv x_{i_2} a\pmod p$

или

$(x_{i_1} - x_{i_2}) a \equiv 0\pmod p$.

Так как $a$ взаимно просто с $p$, то последнее равенство равносильно тому, что

$x_{i_1} - x_{i_2} \equiv 0\pmod p$ или $x_{i_1} \equiv x_{i_2}\pmod p$.

Это противоречит тому, что числа $x_1, \dots, x_{\varphi(p)}$ попарно различны по модулю $p$.

Перемножим все сравнения вида $x_i a \equiv x_j\pmod p$. Получим:

$x_1 \cdots x_{\varphi(p)} a^{\varphi(p)} \equiv x_1 \cdots x_{\varphi(p)}\pmod p$

или

$x_1 \cdots x_{\varphi(p)} (a^{\varphi(p)}-1) \equiv 0\pmod p$.

Так как число $x_1 \cdots x_{\varphi(p)}$ взаимно просто с $p$, то последнее сравнение равносильно тому, что

$a^{\varphi(p)}-1 \equiv 0\pmod p$

или

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

В частном случае, когда $p$ простое, теорема Эйлера превращается в так называемую малую теорему Ферма:

Малая теорема Ферма

Если $p$ - простое число и $a$ - произвольное целое число, не делящееся на $p$, то $a^{p-1} \equiv 1 \pmod p$.

Следствие.

В кольце $Z_p$ классов вычетов по модулю $p$ из $(\bar a, p) = 1$ следует, что $a^{-1} = a^{-{\varphi}(p)-1}$.

Таким образом, для вычисления мультипликативного обратного к классу $a$ по модулю $p$ в случае, когда $(\bar a, p) = 1$, достаточно $\bar a$ возвести в степень $k$, где $k = p-2$, если $p$ – простое число, и $k = {{\varphi}(p)-1}$ в противном случае.

При таком методе вычисления мультипликативного обратного элемента задача сводится к цепочке умножений и делений с остатком на модуль $p$. Эта задача решается без особых трудностей, если наименьший положительный вычет $a \in \bar a$, где $(\bar a, p) = 1$, представлен в СОК.

Однако, вообще говоря, ${{\varphi}(p)-1}$ не является наименьшим показателем степени, для которого $(\bar a)^{-1} = (\bar a)^{{\varphi}(p)-1}$.