Модулярная логарифметика — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
 
Строка 40: Строка 40:
 
Исходя из понятия первообразного корня операция умножения по модулю <math>p</math> в [[Система остаточных классов|модулярной арифметике]] может быть отображена на операцию сложения по модулю <math>p-1</math> по следующей формуле:
 
Исходя из понятия первообразного корня операция умножения по модулю <math>p</math> в [[Система остаточных классов|модулярной арифметике]] может быть отображена на операцию сложения по модулю <math>p-1</math> по следующей формуле:
 
:<math>|x_{j}\cdot x_{k}|_{p} \cong w^{|i_{j}+i_{k}|_{p-1}}</math>
 
:<math>|x_{j}\cdot x_{k}|_{p} \cong w^{|i_{j}+i_{k}|_{p-1}}</math>
 +
 +
== См. также ==
 +
* [[Первообразный корень по модулю]]

Текущая версия на 08:42, 9 декабря 2013

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

См. также

Источник — «https://vscripts.ru/w/index.php?title=Модулярная_логарифметика&oldid=791»