Модулярная логарифметика — различия между версиями

Версия 15:01, 3 июня 2013

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

Первообразный корень

Первообразным корнем $w$ по модулю $p$ (другое название примитивный корень) называется целое число, возведение, которого в степень $0, 1, 2, ..., (p-2)$ дает неповторяющиеся вычеты по модулю $p$ .

Замечание: Первообразный корень в нашей нотации существует только в случае если $p$ - простое число.

Пример: Число $3$ является первообразным корнем по модулю $7$ . Чтобы в этом убедиться, достаточно каждое число от $1$ до $6$ представить как некоторую степень тройки по модулю $7$ :

$3^0 \equiv 1\ \pmod 7$

$3^1 \equiv 3\ \pmod 7$

$3^2 \equiv 2\ \pmod 7$

$3^3 \equiv 6\ \pmod 7$

$3^4 \equiv 4\ \pmod 7$

$3^5 \equiv 5\ \pmod 7$

Дискретный логарифм

Пусть $w$ – первообразный корень конечного поля $GF(p)$ . Дискретным логарифмом по основанию $w$ над $GF(p)$ будем называть функцию аргумента $x$ , заданную формулой:

$lg_{w}|x|_{p} = \begin{cases}inf,&\text{if } |x|_{p} = 0\\ ind_{w}|x|_{p},&\text{if } |x|_{p} \neq 0\\ \end{cases}$

здесь:

$inf$ - элемент не являющийся элементом кольца $Z_p$ , так называемая "сингулярность"
$ind_{w}|x|_{p}$ - индекс вычета $|x|_{p}$ , такой что $|w^{ind_{w}|x|_{p}}|_{p} = |x|_{p}$

Пример: Найдем дискретные логарифмы для $p = 7$

$lg_{3}|0|_{7} = inf$

$lg_{3}|1|_{7} = 0$

$lg_{3}|2|_{7} = 2$

$lg_{3}|3|_{7} = 1$

$lg_{3}|4|_{7} = 4$

$lg_{3}|5|_{7} = 5$

$lg_{3}|6|_{7} = 3$

Варианты использования

Исходя из понятия первообразного корня операция умножения по модулю $p$ в модулярной арифметике может быть отображена на операцию сложения по модулю $p-1$ по следующей формуле:

$|x_{j}\cdot x_{k}|_{p} \cong w^{|i_{j}+i_{k}|_{p-1}}$

@@ Строка 35: / Строка 35: @@
 :<math>lg_{3}|5|_{7} = 5</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>

Модулярная логарифметика — различия между версиями

Версия 15:01, 3 июня 2013

Первообразный корень

Дискретный логарифм

Варианты использования

Навигация

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

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

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты