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

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