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

Isaeva в 15:00, 24 июня 2015

2015-06-24T15:00:17Z

Isaeva в 14:43, 24 июня 2015

2015-06-24T14:43:17Z

Isaeva в 15:15, 4 февраля 2015

2015-02-04T15:15:42Z

Isaeva в 12:25, 4 февраля 2015

2015-02-04T12:25:15Z

Isaeva в 12:56, 23 января 2015

2015-01-23T12:56:52Z

Isaeva в 17:22, 4 сентября 2014

2014-09-04T17:22:17Z

Isaeva в 17:19, 4 сентября 2014

2014-09-04T17:19:30Z

Isaeva в 17:15, 4 сентября 2014

2014-09-04T17:15:19Z

Isaeva: Новая страница: «Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-…»

2014-09-04T16:59:02Z

Новая страница: «Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-…»

Новая страница

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

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

← Предыдущая		Версия 15:00, 24 июня 2015
Строка 29:		Строка 29:


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


Строка 104:		Строка 104:

	:<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>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>, причём сложение (а, следовательно, и вычитание) и умножение выполняются покомпонентно.

@@ Строка 2: / Строка 2: @@
-'''Теорема.'''
+'''Теорема'''
-Пусть <math>\bar a \in Z_p</math>, тогда класс <math>a</math> имеет мультипликативный обратный элемент по модулю <math>p</math> тогда и только тогда, когда <math>(a_1, p) = 1</math>.
+Пусть <math>\bar a \in Z_p</math>, тогда класс <math>a</math> имеет мультипликативный обратный элемент по модулю <math>p</math> тогда и только тогда, когда <math>(a, p) = 1</math>.
-'''Теорема.'''
+'''Теорема'''
 Характеристика <math>\lambda</math> конечного поля – простое число.
@@ Строка 39: / Строка 39: @@
 Доказательство теоремы достаточно простое, возможны различные варианты. Приведем здесь теоретико-числовое доказательство.
-''Доказательство.''
+''Доказательство''
 Пусть <math>x_1, \dots, x_{\varphi(p)}</math> — все различные натуральные числа, меньшие <math>p</math> и взаимно простые с ним.
@@ Строка 73: / Строка 73: @@
-'''Следствие.'''
+'''Следствие'''
 В кольце <math>Z_p</math> классов вычетов по модулю <math>p</math> из <math>(\bar a, p) = 1</math> следует, что <math>a^{-1} = a^{-{\varphi}(p)-1}</math>.

← Предыдущая		Версия 15:15, 4 февраля 2015
Строка 84:		Строка 84:

	Однако, вообще говоря, <math>{{\varphi}(p)-1}</math> не является наименьшим показателем степени, для которого <math>(\bar a)^{-1} = (\bar a)^{{\varphi}(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>.

@@ Строка 1: / Строка 1: @@
 Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-кольце <math>Z_p</math>.
 Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.
-'''Первый способ'''
-'''Второй способ'''
+''Второй способ''
 Напомним теорему Эйлера.
@@ Строка 25: / Строка 39: @@
 Доказательство теоремы достаточно простое, возможны различные варианты. Приведем здесь теоретико-числовое доказательство.
-Доказательство.
+''Доказательство.''
 Пусть <math>x_1, \dots, x_{\varphi(p)}</math> — все различные натуральные числа, меньшие <math>p</math> и взаимно простые с ним.
@@ Строка 57: / Строка 71: @@
 Если <math>p</math> - простое число и <math>a</math> - произвольное целое число, не делящееся на <math>p</math>, то <math>a^{p-1} \equiv 1 \pmod p </math>.

@@ Строка 12: / Строка 12: @@
 '''Определение'''
-Функция Эйлера <math>phi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
+Функция Эйлера <math>\varphi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
@@ Строка 20: / Строка 20: @@
 '''Tеоремa Эйлера'''
-Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{phi(p)} \equiv 1 \pmod p</math>, где <math>phi (n)</math> - функция Эйлера.
+Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{\varphi(p)} \equiv 1 \pmod p</math>, где <math>\varphi (n)</math> - функция Эйлера.
@@ Строка 27: / Строка 27: @@
 Доказательство.
-Пусть <math>x_1, \dots, x_{phi(p)}</math> — все различные натуральные числа, меньшие <math>p</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>.
@@ Строка 40: / Строка 40: @@
 Так как <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_1, \dots, x_{\varphi(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_{\varphi(p)} a^{\varphi(p)} \equiv x_1 \cdots x_{\varphi(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_{\varphi(p)} (a^{\varphi(p)}-1) \equiv 0\pmod p</math>.
-Так как число <math>x_1 \cdots x_{phi(p)}</math> взаимно просто с <math>p</math>, то последнее сравнение равносильно тому, что
+Так как число <math>x_1 \cdots x_{\varphi(p)}</math> взаимно просто с <math>p</math>, то последнее сравнение равносильно тому, что
-: <math>a^{phi(p)}-1 \equiv 0\pmod p</math>
+: <math>a^{\varphi(p)}-1 \equiv 0\pmod p</math>
 или
-:<math>a^{phi(p)} \equiv 1\pmod p</math>.
+:<math>a^{\varphi(p)} \equiv 1\pmod p</math>.

← Предыдущая		Версия 17:22, 4 сентября 2014
Строка 3:		Строка 3:
	Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.		Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.

		+	'''Первый способ'''
		+
		+
		+	'''Второй способ'''
		+
		+	Напомним теорему Эйлера.

	'''Определение'''		'''Определение'''

← Предыдущая		Версия 17:15, 4 сентября 2014
Строка 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>.