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

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

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

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

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

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