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

Версия 20:15, 4 сентября 2014

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

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

Определение

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

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

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

Если $a$ и $p$ взаимно просты, то $a^{phi(p)} \equiv 1 \pmod p$ , где $phi (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_{phi(p)}$ попарно различны по модулю $p$ .

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

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

или

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

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

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

или

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

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

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

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

@@ Строка 2: / Строка 2: @@
 Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.
+'''Определение'''
+Функция Эйлера <math>phi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
+Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с <math>n</math> равен единице.
+'''Tеоремa Эйлера'''
+Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{phi(p)} \equiv 1 \pmod p</math>, где <math>phi (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_{phi(p)}</math> попарно различны по модулю <math>p</math>.
+Перемножим все сравнения вида <math>x_i a \equiv x_j\pmod p</math>. Получим:
+: <math>x_1 \cdots x_{phi(p)} a^{phi(p)} \equiv x_1 \cdots x_{phi(p)}\pmod p</math>
+или
+: <math>x_1 \cdots x_{phi(p)} (a^{phi(p)}-1) \equiv 0\pmod p</math>.
+Так как число <math>x_1 \cdots x_{phi(p)}</math> взаимно просто с <math>p</math>, то последнее сравнение равносильно тому, что
+: <math>a^{phi(p)}-1 \equiv 0\pmod p</math>
+или
+:<math>a^{phi(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>.

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

Версия 20:15, 4 сентября 2014

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

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

Варианты

Просмотры

Действия

Поиск

Навигация