Модулярная логарифметика - История изменений

Turbo в 08:42, 9 декабря 2013

2013-12-09T08:42:14Z

Turbo в 15:01, 3 июня 2013

2013-06-03T15:01:06Z

Turbo в 14:51, 3 июня 2013

2013-06-03T14:51:53Z

Turbo в 14:24, 3 июня 2013

2013-06-03T14:24:04Z

Turbo в 14:20, 3 июня 2013

2013-06-03T14:20:24Z

Turbo: Новая страница: «'''Модулярная логарифметика''' (более полное название '''Логарифмическая система остаточн…»

2013-06-03T13:50:39Z

Новая страница: «'''Модулярная логарифметика''' (более полное название '''Логарифмическая система остаточн…»

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

'''Модулярная логарифметика''' (более полное название '''Логарифмическая система остаточных классов''', в английском варианте '''The Residue Logarithmic Number System''') - система счисления основанная на [[Система остаточных классов|системе остаточных классов]], в которой числа представлены в виде дискретных логарифмов от соответствующих вычетов.

← Предыдущая		Версия 08:42, 9 декабря 2013
Строка 40:		Строка 40:
	Исходя из понятия первообразного корня операция умножения по модулю <math>p</math> в [[Система остаточных классов\|модулярной арифметике]] может быть отображена на операцию сложения по модулю <math>p-1</math> по следующей формуле:		Исходя из понятия первообразного корня операция умножения по модулю <math>p</math> в [[Система остаточных классов\|модулярной арифметике]] может быть отображена на операцию сложения по модулю <math>p-1</math> по следующей формуле:
	:<math>\|x_{j}\cdot x_{k}\|_{p} \cong w^{\|i_{j}+i_{k}\|_{p-1}}</math>		:<math>\|x_{j}\cdot x_{k}\|_{p} \cong w^{\|i_{j}+i_{k}\|_{p-1}}</math>
		+
		+	== См. также ==
		+	* [[Первообразный корень по модулю]]

← Предыдущая		Версия 15:01, 3 июня 2013
Строка 35:		Строка 35:
	:<math>lg_{3}\|5\|_{7} = 5</math>		:<math>lg_{3}\|5\|_{7} = 5</math>
	:<math>lg_{3}\|6\|_{7} = 3</math>		:<math>lg_{3}\|6\|_{7} = 3</math>
		+
		+	== Варианты использования ==
		+
		+	Исходя из понятия первообразного корня операция умножения по модулю <math>p</math> в [[Система остаточных классов\|модулярной арифметике]] может быть отображена на операцию сложения по модулю <math>p-1</math> по следующей формуле:
		+	:<math>\|x_{j}\cdot x_{k}\|_{p} \cong w^{\|i_{j}+i_{k}\|_{p-1}}</math>

← Предыдущая		Версия 14:51, 3 июня 2013
Строка 18:		Строка 18:

	Пусть <math>w</math> – первообразный корень конечного поля <math>GF(p)</math>. Дискретным логарифмом по основанию <math>w</math> над <math>GF(p)</math> будем называть функцию аргумента <math>x</math>, заданную формулой:		Пусть <math>w</math> – первообразный корень конечного поля <math>GF(p)</math>. Дискретным логарифмом по основанию <math>w</math> над <math>GF(p)</math> будем называть функцию аргумента <math>x</math>, заданную формулой:
		+
		+	<math>lg_{w}\|x\|_{p} = \begin{cases}inf,&\text{if } \|x\|_{p} = 0\\
		+	ind_{w}\|x\|_{p},&\text{if } \|x\|_{p} \neq 0\\
		+	\end{cases}</math>
		+
		+	здесь:
		+	* <math>inf</math> - элемент не являющийся элементом кольца <math>Z_p</math>, так называемая "сингулярность"
		+	* <math>ind_{w}\|x\|_{p}</math> - индекс вычета <math>\|x\|_{p}</math>, такой что <math>\|w^{ind_{w}\|x\|_{p}}\|_{p} = \|x\|_{p}</math>
		+
		+	''Пример'': Найдем дискретные логарифмы для <math>p = 7</math>
		+	:<math>lg_{3}\|0\|_{7} = inf</math>
		+	:<math>lg_{3}\|1\|_{7} = 0</math>
		+	:<math>lg_{3}\|2\|_{7} = 2</math>
		+	:<math>lg_{3}\|3\|_{7} = 1</math>
		+	:<math>lg_{3}\|4\|_{7} = 4</math>
		+	:<math>lg_{3}\|5\|_{7} = 5</math>
		+	:<math>lg_{3}\|6\|_{7} = 3</math>

@@ Строка 4: / Строка 4: @@
 Первообразным корнем <math>w</math> по модулю <math>p</math> (другое название примитивный корень) называется целое число, возведение, которого в степень <math>0, 1, 2, ..., (p-2)</math> дает неповторяющиеся вычеты по модулю <math>p</math>.
 == Дискретный логарифм ==
 Пусть <math>w</math> – первообразный корень конечного поля <math>GF(p)</math>. Дискретным логарифмом по основанию <math>w</math> над <math>GF(p)</math> будем называть функцию аргумента <math>x</math>, заданную формулой:

← Предыдущая		Версия 14:20, 3 июня 2013
Строка 1:		Строка 1:
	'''Модулярная логарифметика''' (более полное название '''Логарифмическая система остаточных классов''', в английском варианте '''The Residue Logarithmic Number System''') - система счисления основанная на [[Система остаточных классов\|системе остаточных классов]], в которой числа представлены в виде дискретных логарифмов от соответствующих вычетов.		'''Модулярная логарифметика''' (более полное название '''Логарифмическая система остаточных классов''', в английском варианте '''The Residue Logarithmic Number System''') - система счисления основанная на [[Система остаточных классов\|системе остаточных классов]], в которой числа представлены в виде дискретных логарифмов от соответствующих вычетов.
		+
		+	== Первообразный корень ==
		+
		+	Первообразным корнем <math>w</math> по модулю <math>p</math> (другое название примитивный корень) называется целое число, возведение, которого в степень <math>0, 1, 2, ..., (p-2)</math> дает неповторяющиеся вычеты по модулю <math>p</math>.
		+
		+	== Дискретный логарифм ==
		+
		+	Пусть <math>w</math> – первообразный корень конечного поля <math>GF(p)</math>. Дискретным логарифмом по основанию <math>w</math> над <math>GF(p)</math> будем называть функцию аргумента <math>x</math>, заданную формулой: