Модулярная логарифметика
Turbo (обсуждение | вклад) |
Turbo (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
Первообразным корнем <math>w</math> по модулю <math>p</math> (другое название примитивный корень) называется целое число, возведение, которого в степень <math>0, 1, 2, ..., (p-2)</math> дает неповторяющиеся вычеты по модулю <math>p</math>. | Первообразным корнем <math>w</math> по модулю <math>p</math> (другое название примитивный корень) называется целое число, возведение, которого в степень <math>0, 1, 2, ..., (p-2)</math> дает неповторяющиеся вычеты по модулю <math>p</math>. | ||
| + | |||
| + | ''Замечание'': Первообразный корень в нашей нотации существует только в случае если <math>p</math> - простое число. | ||
| + | |||
| + | ''Пример'': Число <math>3</math> является первообразным корнем по модулю <math>7</math>. Чтобы в этом убедиться, достаточно каждое число от <math>1</math> до <math>6</math> представить как некоторую степень тройки по модулю <math>7</math>: | ||
| + | :<math>3^0 \equiv 1\ \pmod 7</math> | ||
| + | :<math>3^1 \equiv 3\ \pmod 7</math> | ||
| + | :<math>3^2 \equiv 2\ \pmod 7</math> | ||
| + | :<math>3^3 \equiv 6\ \pmod 7</math> | ||
| + | :<math>3^4 \equiv 4\ \pmod 7</math> | ||
| + | :<math>3^5 \equiv 5\ \pmod 7</math> | ||
== Дискретный логарифм == | == Дискретный логарифм == | ||
Пусть <math>w</math> – первообразный корень конечного поля <math>GF(p)</math>. Дискретным логарифмом по основанию <math>w</math> над <math>GF(p)</math> будем называть функцию аргумента <math>x</math>, заданную формулой: | Пусть <math>w</math> – первообразный корень конечного поля <math>GF(p)</math>. Дискретным логарифмом по основанию <math>w</math> над <math>GF(p)</math> будем называть функцию аргумента <math>x</math>, заданную формулой: | ||
Версия 17:24, 3 июня 2013
Модулярная логарифметика (более полное название Логарифмическая система остаточных классов, в английском варианте The Residue Logarithmic Number System) - система счисления основанная на системе остаточных классов, в которой числа представлены в виде дискретных логарифмов от соответствующих вычетов.
Первообразный корень
Первообразным корнем 
по модулю 
(другое название примитивный корень) называется целое число, возведение, которого в степень 
дает неповторяющиеся вычеты по модулю .
Замечание: Первообразный корень в нашей нотации существует только в случае если - простое число.
Пример: Число 
является первообразным корнем по модулю 
. Чтобы в этом убедиться, достаточно каждое число от 
до 
представить как некоторую степень тройки по модулю :
Дискретный логарифм
Пусть – первообразный корень конечного поля 
. Дискретным логарифмом по основанию над будем называть функцию аргумента 
, заданную формулой:
