Модулярная логарифметика

Модулярная логарифметика (более полное название Логарифмическая система остаточных классов, в английском варианте 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}}$

См. также

• Первообразный корень по модулю