Логарифм Цеха

Инструмент для быстрой арифметики конечных полей

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

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

Определение

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

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

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

${\displaystyle Z_{\alpha }(n)=\log _{\alpha }(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 }$

где — целое число, удовлетворяющее , то есть для поля характеристики 2, и для поля нечетной характеристики с элементами. ${\displaystyle e}$ ${\displaystyle \alpha ^{e}=-1}$ ${\displaystyle e=0}$ ${\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 }$

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

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

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

• Флетчер, Алан; Миллер, Джеффри Чарльз Перси ; Розенхед, Луис (1946) [1943]. Указатель математических таблиц (1-е изд.). Blackwell Scientific Publications Ltd. , Оксфорд / Макгроу-Хилл , Нью-Йорк.
• Conway, John Horton (1968). Churchhouse, Robert F.; Herz, J.-C. (ред.). «Табулирование некоторой информации, касающейся конечных полей». Computers in Mathematical Research . Amsterdam: North-Holland Publishing Company : 37–50. MR  0237467.
• Lam, Clement Wing Hong ; McKay, John KS (1973-11-01). "Алгоритм 469: Арифметика над конечным полем [A1]". Сообщения ACM . Сборник алгоритмов ACM (CALGO). 16 (11). Ассоциация вычислительной техники (ACM): 699. doi : 10.1145/355611.362544 . ISSN  0001-0782. S2CID  62794130. toms/469.[1] [2] [3]
• Кюн, Клаус (2008). «CF Gauß und die Logarithmen» (PDF) (на немецком языке). Аллинг-Бибург, Германия. Архивировано (PDF) из оригинала 14 июля 2018 г. Проверено 14 июля 2018 г.