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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
 
(не показаны 3 промежуточные версии этого же участника)
Строка 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>, заданную формулой:
 +
 +
<math>lg_{w}|x|_{p} = \begin{cases}inf,&\text{if  } |x|_{p} = 0\\
 +
ind_{w}|x|_{p},&\text{if  } |x|_{p} \neq 0\\
 +
\end{cases}</math>
 +
 +
здесь:
 +
* <math>inf</math> - элемент не являющийся элементом кольца <math>Z_p</math>, так называемая "сингулярность"
 +
* <math>ind_{w}|x|_{p}</math> - индекс вычета <math>|x|_{p}</math>, такой что <math>|w^{ind_{w}|x|_{p}}|_{p} = |x|_{p}</math>
 +
 +
''Пример'': Найдем дискретные логарифмы для <math>p = 7</math>
 +
:<math>lg_{3}|0|_{7} = inf</math>
 +
:<math>lg_{3}|1|_{7} = 0</math>
 +
:<math>lg_{3}|2|_{7} = 2</math>
 +
:<math>lg_{3}|3|_{7} = 1</math>
 +
:<math>lg_{3}|4|_{7} = 4</math>
 +
:<math>lg_{3}|5|_{7} = 5</math>
 +
:<math>lg_{3}|6|_{7} = 3</math>
 +
 +
== Варианты использования ==
 +
 +
Исходя из понятия первообразного корня операция умножения по модулю <math>p</math> в [[Система остаточных классов|модулярной арифметике]] может быть отображена на операцию сложения по модулю <math>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»