Логарифм Зекса - Zechs logarithm

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

Логарифмы Зеха названы в честь Юлий Зех,^[1][2][3][4] и также называются Логарифмы Якоби,^[5] после Карл Дж. Дж. Якоби кто использовал их для теоретико-числовой расследования.^[6]

Определение

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

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

или эквивалентно

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

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

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

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

${\displaystyle n+(-\infty )=-\infty }$

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

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

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

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

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

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

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

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

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

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

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

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

Обратите внимание, что для полей характеристики два,

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

Использует

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

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

Примеры

Позволять α ∈ GF (2³) быть корнем примитивный многочлен Икс³ + Икс² + 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.

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

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

Рекомендации

1. Зах, Юлий Август Кристоф (1849). Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из собрания Vega – Hülße) 1-е изд.). Лейпциг: Weidmann'sche Buchhandlung. В архиве из оригинала на 2018-07-14. Получено 2018-07-14. Также входит в состав: Фрайхер фон Вега, Георг (1849). Hülße, Юлиус Амброзиус; Зах, Юлий Август Кристоф (ред.). Sammlung Mathematischer Tafeln (на немецком языке) (Полностью переработанная ред.). Лейпциг: Weidmann'sche Buchhandlung. Bibcode:1849смт..книга ..... В. В архиве из оригинала на 2018-07-14. Получено 2018-07-14.
2. Зах, Юлий Август Кристоф (1863) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из собрания Vega – Hülße) 2-е изд.). Берлин: Weidmann'sche Buchhandlung. В архиве из оригинала на 2018-07-14. Получено 2018-07-13.
3. Зах, Юлий Август Кристоф (1892) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из коллекции Vega – Hülße) 3-е изд.). Берлин: Weidmann'sche Buchhandlung. В архиве из оригинала на 2018-07-14. Получено 2018-07-13.
4. Зах, Юлий Август Кристоф (1910) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из собрания Vega – Hülße) 4-е изд.). Берлин: Weidmann'sche Buchhandlung. В архиве из оригинала на 2018-07-14. Получено 2018-07-13.
5. Лидл, Рудольф; Нидеррайтер, Харальд (1997). Конечные поля (2-е изд.). Издательство Кембриджского университета. ISBN  978-0-521-39231-0.
6. Якоби, Карл Густав Джейкоб (1846). "Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie". Журнал für die reine und angewandte Mathematik (на немецком). 1846 (30): 166–182. Дои:10.1515 / crll.1846.30.166. ISSN  0075-4102. S2CID  120615565. (NB. Также часть "Gesammelte Werke", том 6, страницы 254–274.)

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

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