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

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