Логарифм Заха

редактировать

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

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

СОДЕРЖАНИЕ

1 Определение
2 использования
3 Примеры
4 См. Также
5 ссылки
6 Дальнейшее чтение

Определение

Учитывая примитивный элемент конечного поля, логарифм Зека относительно основания определяется уравнением ${\ displaystyle \ alpha}$ $\альфа$ ${\ displaystyle \ alpha}$ $\альфа$

{\ Displaystyle \ альфа ^ {Z _ {\ альфа} (п)} = 1+ \ альфа ^ {п},}

{\ Displaystyle \ альфа ^ {Z _ {\ альфа} (п)} = 1+ \ альфа ^ {п},}

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

{\ displaystyle Z _ {\ alpha} (n) = \ log _ {\ alpha} (1+ \ alpha ^ {n}).}

{\ displaystyle Z _ {\ alpha} (n) = \ log _ {\ alpha} (1+ \ alpha ^ {n}).}

Выбор базы обычно опускается из обозначений, когда это ясно из контекста. ${\ displaystyle \ alpha}$ $\альфа$

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

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

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

{\ Displaystyle п + (- \ infty) = - \ infty}

п + (- \ infty) = - \ infty

{\ Displaystyle Z _ {\ альфа} (- \ infty) = 0}

Z _ {\ alpha} (- \ infty) = 0

{\ Displaystyle Z _ {\ альфа} (е) = - \ infty}

Z _ {\ alpha} (e) = - \ infty

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

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

{\ displaystyle \ alpha ^ {m} + \ alpha ^ {n} = \ alpha ^ {m} \ cdot (1+ \ alpha ^ {nm}) = \ alpha ^ {m} \ cdot \ alpha ^ {Z ( нм)} = \ альфа ^ {m + Z (нм)}}

\ alpha ^ {m} + \ alpha ^ {n} = \ alpha ^ {m} \ cdot (1+ \ alpha ^ {{nm}}) = \ alpha ^ {m} \ cdot \ alpha ^ {{Z ( нм)}} = \ alpha ^ {{m + Z (нм)}}

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

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

{\ Displaystyle \ альфа ^ {м} - \ альфа ^ {п} = \ альфа ^ {м} + (- \ альфа ^ {п}) = \ альфа ^ {м + Z (е + нм)}}

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

{\ Displaystyle \ альфа ^ {м} \ CDOT \ альфа ^ {п} = \ альфа ^ {м + п}}

\ альфа ^ {м} \ cdot \ альфа ^ {п} = \ альфа ^ {{м + п}}

{\ Displaystyle \ влево (\ альфа ^ {м} \ вправо) ^ {- 1} = \ альфа ^ {- м}}

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

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

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

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

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

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

{\ displaystyle Z _ {\ alpha} (n) = m \ iff Z _ {\ alpha} (m) = n}

{\ displaystyle Z _ {\ alpha} (n) = m \ iff Z _ {\ alpha} (m) = n}

Использует

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

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

Примеры

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

Преобразование от экспоненциального к полиномиальному представлению дается формулой

{\ Displaystyle \ альфа ^ {3} = \ альфа ^ {2} +1}

\ alpha ^ {3} = \ alpha ^ {2} +1

(как показано выше)

{\ Displaystyle \ альфа ^ {4} = \ альфа ^ {3} \ альфа = (\ альфа ^ {2} +1) \ альфа = \ альфа ^ {3} + \ альфа = \ альфа ^ {2} + \ альфа +1}

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

{\ Displaystyle \ альфа ^ {5} = \ альфа ^ {4} \ альфа = (\ альфа ^ {2} + \ альфа +1) \ альфа = \ альфа ^ {3} + \ альфа ^ {2} + \ альфа = \ альфа ^ {2} +1+ \ альфа ^ {2} + \ альфа = \ альфа +1}

\ alpha ^ {5} = \ alpha ^ {4} \ alpha = (\ alpha ^ {2} + \ alpha +1) \ alpha = \ alpha ^ {3} + \ alpha ^ {2} + \ alpha = \ альфа ^ {2} +1+ \ альфа ^ {2} + \ альфа = \ альфа +1

{\ Displaystyle \ альфа ^ {6} = \ альфа ^ {5} \ альфа = (\ альфа +1) \ альфа = \ альфа ^ {2} + \ альфа}

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

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

{\ Displaystyle \ альфа ^ {6} + \ альфа ^ {3} = \ альфа ^ {6 + Z (-3)} = \ альфа ^ {6 + Z (4)} = \ альфа ^ {6 + 6} = \ alpha ^ {12} = \ alpha ^ {5}}

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

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

{\ Displaystyle \ альфа ^ {6} + \ альфа ^ {3} = \ альфа ^ {3 + Z (3)} = \ альфа ^ {3 + 2} = \ альфа ^ {5}}

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

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

{\ Displaystyle \ альфа ^ {6} + \ альфа ^ {3} = (\ альфа ^ {2} + \ альфа) + (\ альфа ^ {2} +1) = \ альфа + 1 = \ альфа ^ {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.
Лам, Клемент Винг Хонг ; Маккей, Джон К.С. (1973-11-01). «Алгоритм 469: Арифметика над конечным полем [A1]». Коммуникации ACM. Собраны алгоритмы ACM (CALGO). Ассоциация вычислительной техники (ACM). 16 (11): 699. DOI : 10,1145 / 355611,362544. ISSN 0001-0782. S2CID 62794130. Томы / 469. [1] [2] [3]
Кюн, Клаус (2008). "CF Gauß und die Logarithmen" (PDF) (на немецком языке). Аллинг-Бибург, Германия. Архивировано (PDF) из оригинала на 2018-07-14. Проверено 14 июля 2018.