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

Текущая версия на 15:00, 24 июня 2015

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

Теорема

Пусть $\bar a \in Z_p$ , тогда класс $a$ имеет мультипликативный обратный элемент по модулю $p$ тогда и только тогда, когда $(a, 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}$ .

Разложение кольца вычетов

Из китайской теоремы об остатках следует

Утверждение

Пусть $p = n_{1}^{l_1} \cdot n_{2}^{l_2} \cdot \ldots \cdot n_{k}^{l_k}$ - каноническое представление числа $p$ . Тогда функция, которая каждому классу $\bar x \in Z_m$ ставит в соответствие кортеж $(x_1, x_2, \ldots, x_k)$ , где $x \equiv x_i \pmod {p_{i}^{l_i}}, i=1, \ldots, k$ , является кольцевым изоморфизмом кольца $Z_p$ класса вычетов по модулю $p$ и кольца кортежей вида $(x_1, x_2, \ldots, x_k)$ , где $\bar x \in Z_{p_i^k}, i=1, \ldots, k$ .

Более того, если обозначить через $*$ любую из кольцевых операций $+$ или $\cdot$ , то

$(x_1, x_2, \ldots, x_k)*(y_1, y_2, \ldots, y_k) = (x_1 * y_1, x_2 * y_2, \ldots, x_k * y_k)$ .

Таким образом,

$Z_p \cong Z_{n_1}^{l_1} \times Z_{n_2}^{l_2} \times \ldots \times Z_{n_k}^{l_k}$ ,

т.е. кольцо классов вычетов по модулю $p$ раскладывается в прямое произведение колец классов вычетов по модулям $n_{1}^{l_1}, n_{2}^{l_2}, \ldots, n_{k}^{l_k}$ . Это разложение колец индуцирует разложение групп их обратимых элементов:

$U_p \cong U_{n_1}^{l_1} \times U_{n_2}^{l_2} \times \ldots \times U_{n_k}^{l_k}$ .

Можно сделать вывод о том, что произвольное целое положительное число $A, 0 < A < P$ , где $p = p_1 \cdot p_2 \cdot \ldots \cdot p_k$ и $(p_i,p_j) = 1$ для $i \not = j$ , однозначно представимо своими наименьшими неотрицательными остатками по модулям $p_i$ , причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.

@@ Строка 1: / Строка 1: @@
 Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-кольце <math>Z_p</math>.
+'''Теорема'''
+Пусть <math>\bar a \in Z_p</math>, тогда класс <math>a</math> имеет мультипликативный обратный элемент по модулю <math>p</math> тогда и только тогда, когда <math>(a, p) = 1</math>.
+'''Теорема'''
+Характеристика <math>\lambda</math> конечного поля – простое число.
 Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.
+''Первый способ''
+Из условия <math>(a, p) = 1</math> получаем <math>a \cdot x + p \cdot y = 1</math> или <math>a \cdot x \equiv 1 \pmod{p}</math> и, следовательно, <math>x</math> – мультипликативный обратный к <math>a</math> по модулю <math>p</math>.
+''Второй способ''
+Напомним теорему Эйлера.
+'''Определение'''
+Функция Эйлера <math>\varphi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
+Т.е. это количество таких натуральных чисел из отрезка <math>[1; n]</math>, наибольший общий делитель (НОД) которых с <math>n</math> равен единице.
+'''Tеоремa Эйлера'''
+Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{\varphi(p)} \equiv 1 \pmod p</math>, где <math>\varphi (n)</math> - функция Эйлера.
+Доказательство теоремы достаточно простое, возможны различные варианты. Приведем здесь теоретико-числовое доказательство.
+''Доказательство''
+Пусть <math>x_1, \dots, x_{\varphi(p)}</math> — все различные натуральные числа, меньшие <math>p</math> и взаимно простые с ним.
+Рассмотрим все возможные произведения <math>x_i a</math> для всех <math>i</math> от <math>1</math> до <math>\varphi(p)</math>.
+Поскольку <math>a</math> взаимно просто с <math>p</math> и <math>x_i</math> взаимно просто с <math>p</math>, то и <math>x_i a</math> также взаимно просто с <math>p</math>, то есть <math>x_i a \equiv x_j\pmod p</math> для некоторого <math>j</math>.
+Отметим, что все остатки <math>x_i a</math> при делении на <math>p</math> различны. Действительно, пусть это не так, то существуют такие <math>i_1 \neq i_2</math>, что
+: <math>x_{i_1} a \equiv x_{i_2} a\pmod p</math>
+или
+: <math>(x_{i_1} - x_{i_2}) a \equiv 0\pmod p</math>.
+Так как <math>a</math> взаимно просто с <math>p</math>, то последнее равенство равносильно тому, что
+: <math>x_{i_1} - x_{i_2} \equiv 0\pmod p</math> или <math>x_{i_1} \equiv x_{i_2}\pmod p</math>.
+Это противоречит тому, что числа <math>x_1, \dots, x_{\varphi(p)}</math> попарно различны по модулю <math>p</math>.
+Перемножим все сравнения вида <math>x_i a \equiv x_j\pmod p</math>. Получим:
+: <math>x_1 \cdots x_{\varphi(p)} a^{\varphi(p)} \equiv x_1 \cdots x_{\varphi(p)}\pmod p</math>
+или
+: <math>x_1 \cdots x_{\varphi(p)} (a^{\varphi(p)}-1) \equiv 0\pmod p</math>.
+Так как число <math>x_1 \cdots x_{\varphi(p)}</math> взаимно просто с <math>p</math>, то последнее сравнение равносильно тому, что
+: <math>a^{\varphi(p)}-1 \equiv 0\pmod p</math>
+или
+:<math>a^{\varphi(p)} \equiv 1\pmod p</math>.
+В частном случае, когда <math>p</math> простое, теорема Эйлера превращается в так называемую малую теорему Ферма:
+'''Малая теорема Ферма'''
+Если <math>p</math> - простое число и <math>a</math> - произвольное целое число, не делящееся на <math>p</math>, то <math>a^{p-1} \equiv 1 \pmod p </math>.
+'''Следствие'''
+В кольце <math>Z_p</math> классов вычетов по модулю <math>p</math> из <math>(\bar a, p) = 1</math> следует, что <math>a^{-1} = a^{-{\varphi}(p)-1}</math>.
+Таким образом, для вычисления мультипликативного обратного к классу <math>a</math> по модулю <math>p</math> в случае, когда <math>(\bar a, p) = 1</math>, достаточно <math>\bar a</math> возвести в степень <math>k</math>, где <math>k = p-2</math>, если <math>p</math> – простое число, и <math>k = {{\varphi}(p)-1}</math> в противном случае.
+При таком методе вычисления мультипликативного обратного элемента задача сводится к цепочке умножений и делений с остатком на модуль <math>p</math>. Эта задача решается без особых трудностей, если наименьший положительный вычет <math>a \in \bar a</math>, где <math>(\bar a, p) = 1</math>, представлен в СОК.
+Однако, вообще говоря, <math>{{\varphi}(p)-1}</math> не является наименьшим показателем степени, для которого <math>(\bar a)^{-1} = (\bar a)^{{\varphi}(p)-1}</math>.
+''Разложение кольца вычетов''
+Из китайской теоремы об остатках следует
+''Утверждение''
+Пусть <math>p = n_{1}^{l_1} \cdot n_{2}^{l_2} \cdot \ldots \cdot n_{k}^{l_k}</math> - каноническое представление числа <math>p</math>. Тогда функция, которая каждому классу <math>\bar x \in Z_m</math> ставит в соответствие кортеж <math>(x_1, x_2, \ldots, x_k)</math>, где <math> x \equiv x_i \pmod {p_{i}^{l_i}}, i=1, \ldots, k</math>, является кольцевым изоморфизмом кольца <math>Z_p</math> класса вычетов по модулю <math>p</math> и кольца кортежей вида <math>(x_1, x_2, \ldots, x_k)</math>, где <math>\bar x \in Z_{p_i^k}, i=1, \ldots, k</math>.
+Более того, если обозначить через <math>*</math> любую из кольцевых операций <math>+</math> или <math>\cdot</math> , то
+:<math>(x_1, x_2, \ldots, x_k)*(y_1, y_2, \ldots, y_k) = (x_1 * y_1, x_2 * y_2, \ldots, x_k * y_k)</math>.
+Таким образом,
+:<math>Z_p \cong Z_{n_1}^{l_1} \times Z_{n_2}^{l_2} \times \ldots \times Z_{n_k}^{l_k}</math>,
+т.е. кольцо классов вычетов по модулю <math>p</math> раскладывается в прямое произведение колец классов вычетов по модулям <math>n_{1}^{l_1}, n_{2}^{l_2}, \ldots, n_{k}^{l_k}</math>. Это разложение колец индуцирует разложение групп их обратимых элементов:
+:<math>U_p \cong U_{n_1}^{l_1} \times U_{n_2}^{l_2} \times \ldots \times U_{n_k}^{l_k}</math>.
+Можно сделать вывод о том, что произвольное целое положительное число <math>A, 0 < A < P</math>, где <math>p = p_1 \cdot p_2 \cdot \ldots \cdot p_k</math> и <math>(p_i,p_j) = 1</math> для <math>i \not = j</math>, однозначно представимо своими наименьшими неотрицательными остатками по модулям <math>p_i</math>, причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.

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

Текущая версия на 15:00, 24 июня 2015

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты