логарифм Зеха

Логарифмы Зеха используются для реализации сложения в конечных полях , когда элементы представлены как степени генератора. $\alpha$.

Логарифмы Зеха названы в честь Юлия Зеха , и называются также логарифмами Якоби , в честь Карла Г. Дж. Якоби , который использовал их для теоретико-числовых исследований.

Определение

Учитывая примитивный элемент $\alpha$ конечного поля логарифм Цеха по основанию $\alpha$ определяется уравнением

$\alpha ^{Z_{\alpha }(n)}=1+\alpha ^{n},$

который часто переписывают как

$Z_{\alpha }(n)=\log _{\alpha }(1+\alpha ^{n}).$

Выбор базы $\alpha$ обычно опускается из обозначений, если это ясно из контекста.

Если быть более точным, $Z_{\alpha }$ является функцией по целых чисел модулю мультипликативного порядка $\alpha$и принимает значения из того же набора. Для описания каждого элемента удобно формально добавить новый символ $-\infty$, наряду с определениями

$\alpha ^{-\infty }=0$

$n+(-\infty )=-\infty$

$Z_{\alpha }(-\infty )=0$

$Z_{\alpha }(e)=-\infty$

где $e$ является целым числом, удовлетворяющим $\alpha ^{e}=-1$, то есть $e=0$ для поля характеристики 2 , и $e={\frac {q-1}{2}}$ для поля нечетной характеристики с $q$ элементы.

Используя логарифм Зеха, арифметику конечных полей можно выполнить в экспоненциальном представлении:

$\alpha ^{m}+\alpha ^{n}=\alpha ^{m}\cdot (1+\alpha ^{n-m})=\alpha ^{m}\cdot \alpha ^{Z(n-m)}=\alpha ^{m+Z(n-m)}$

$-\alpha ^{n}=(-1)\cdot \alpha ^{n}=\alpha ^{e}\cdot \alpha ^{n}=\alpha ^{e+n}$

$\alpha ^{m}-\alpha ^{n}=\alpha ^{m}+(-\alpha ^{n})=\alpha ^{m+Z(e+n-m)}$

$\alpha ^{m}\cdot \alpha ^{n}=\alpha ^{m+n}$

$\left(\alpha ^{m}\right)^{-1}=\alpha ^{-m}$

$\alpha ^{m}/\alpha ^{n}=\alpha ^{m}\cdot \left(\alpha ^{n}\right)^{-1}=\alpha ^{m-n}$

Эти формулы остаются верными с учетом наших соглашений с символом $-\infty$с оговоркой, что вычитание $-\infty$ является неопределенным. В частности, формулы сложения и вычитания необходимо учитывать. $m=-\infty$ как частный случай.

Это можно распространить на арифметику проективной прямой , введя еще один символ. $+\infty$ удовлетворяющий $\alpha ^{+\infty }=\infty$ и другие правила по мере необходимости.

Для полей характеристики 2

$Z_{\alpha }(n)=m\iff Z_{\alpha }(m)=n$.

Использование

Для достаточно малых конечных полей таблица логарифмов Зеха позволяет особенно эффективно реализовать всю арифметику конечных полей с точки зрения небольшого количества целочисленных сложений/вычитаний и поиска в таблице.

Полезность этого метода снижается для больших полей, где невозможно эффективно хранить таблицу. Этот метод также неэффективен при выполнении очень небольшого количества операций в конечном поле, поскольку на вычисление таблицы тратится больше времени, чем на реальные вычисления.

Примеры

Пусть α ∈ GF(2 ³ ) быть корнем примитивного многочлена x ³ + х ² + 1 . Традиционное представление элементов этого поля — это полиномы от α степени 2 или меньше.

Таблица логарифмов Зеха для этого поля: Z (−∞) = 0 , Z (0) = −∞ , Z (1) = 5 , Z (2) = 3 , Z (3) = 2 , Z (4) знак равно 6 , Z (5) = 1 и Z (6) = 4 . Мультипликативный порядок α равен 7, поэтому экспоненциальное представление работает с целыми числами по модулю 7.

Поскольку α является корнем x ³ + х ² + 1 , то это означает α ³ + а ² + 1 = 0 , или если вспомнить, что, поскольку все коэффициенты принадлежат GF(2), вычитание аналогично сложению, получим α ³ = а ² + 1 .

Преобразование экспоненциального представления в полиномиальное определяется выражением

$\alpha ^{3}=\alpha ^{2}+1$ (как показано выше)

$\alpha ^{4}=\alpha ^{3}\alpha =(\alpha ^{2}+1)\alpha =\alpha ^{3}+\alpha =\alpha ^{2}+\alpha +1$

$\alpha ^{5}=\alpha ^{4}\alpha =(\alpha ^{2}+\alpha +1)\alpha =\alpha ^{3}+\alpha ^{2}+\alpha =\alpha ^{2}+1+\alpha ^{2}+\alpha =\alpha +1$

$\alpha ^{6}=\alpha ^{5}\alpha =(\alpha +1)\alpha =\alpha ^{2}+\alpha$

Использование логарифмов Зеха для вычисления α ⁶ + а ³ :

$\alpha ^{6}+\alpha ^{3}=\alpha ^{6+Z(-3)}=\alpha ^{6+Z(4)}=\alpha ^{6+6}=\alpha ^{12}=\alpha ^{5},$

или, что более эффективно,

$\alpha ^{6}+\alpha ^{3}=\alpha ^{3+Z(3)}=\alpha ^{3+2}=\alpha ^{5},$

и проверяем это в полиномиальном представлении:

$\alpha ^{6}+\alpha ^{3}=(\alpha ^{2}+\alpha )+(\alpha ^{2}+1)=\alpha +1=\alpha ^{5}.$

См. также

• Гауссов логарифм
• Ирландский логарифм — аналогичный метод, полученный эмпирически Перси Ладгейтом.
• Арифметика конечных полей
• Таблица логарифмов

Дальнейшее чтение

• Флетчер, Алан; Миллер, Джеффри Чарльз Перси ; Розенхед, Луи (1946) [1943]. Указатель математических таблиц (1-е изд.). Blackwell Scientific Publications Ltd. , Оксфорд/ МакГроу-Хилл , Нью-Йорк.
• Конвей, Джон Хортон (1968). Черчхаус, Роберт Ф.; Герц, Ж.-К. (ред.). «Таблица некоторой информации, касающейся конечных полей». Компьютеры в математических исследованиях . Амстердам: Издательство Северной Голландии : 37–50. МР   0237467 .
• Лам, Клемент Винг Хонг ; Маккей, Джон К.С. (1 ноября 1973 г.). «Алгоритм 469: Арифметика над конечным полем [A1]» . Коммуникации АКМ . Сборник алгоритмов ACM (CALGO). 16 (11). Ассоциация вычислительной техники (ACM): 699. doi : 10.1145/355611.362544 . ISSN   0001-0782 . S2CID   62794130 . том/469. [1] [2] [3]
• Кюн, Клаус (2008). «CF Гаусс и логарифмы» (PDF) (на немецком языке). Аллинг-Бибург, Германия. Архивировано (PDF) из оригинала 14 июля 2018 г. Проверено 14 июля 2018 г.