Логарифмы Цеха используются для реализации сложения в конечных полях, когда элементы представлены как мощности генератора..
З логарифмы имя Юлиус З , [1] [2] [3] [4] , а также называются Якоби логарифмы , [5] после того, как Карл GJ Jacobi , который использовал их для теории чисел исследований. [6]
Определение
Учитывая примитивный элемент конечного поля, логарифм Цеха относительно основания определяется уравнением
который часто переписывается как
Выбор базы обычно исключается из обозначений, когда это ясно из контекста.
Если быть более точным, является функцией от целых чисел по модулю мультипликативного порядка , и принимает значения из того же набора. Для описания каждого элемента удобно формально добавить новый символ., вместе с определениями
где целое число, удовлетворяющее , это для поля характеристики 2 и для поля нечетной характеристики с элементы.
Используя логарифм Зеха, арифметика конечных полей может быть выполнена в экспоненциальном представлении:
Эти формулы остаются верными с нашими соглашениями с символом , с оговоркой, что вычитание не определено. В частности, формулы сложения и вычитания необходимо рассматривать как частный случай.
Это можно распространить на арифметику проективной прямой , введя еще один символ удовлетворение и другие правила по мере необходимости.
Для полей характеристики два
- .
Использует
Для достаточно маленьких конечных полей таблица логарифмов Зека позволяет особенно эффективно реализовать всю арифметику конечных полей с точки зрения небольшого числа целочисленных сложений / вычитаний и поиска в таблице.
Полезность этого метода уменьшается для больших полей, где невозможно эффективно хранить таблицу. Этот метод также неэффективен при выполнении очень небольшого числа операций в конечном поле, поскольку на вычисление таблицы уходит больше времени, чем на фактическое вычисление.
Примеры
Пусть α ∈ GF (2 3 ) - корень примитивного многочлена x 3 + x 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.
Поскольку α является корнем из x 3 + x 2 + 1, это означает, что α 3 + α 2 + 1 = 0 , или, если вспомнить, что, поскольку все коэффициенты находятся в GF (2), вычитание аналогично сложению, получаем α 3 = α 2 + 1 .
Преобразование от экспоненциального к полиномиальному представлению дается формулой
- (как показано выше)
Используя логарифмы Зека для вычисления α 6 + α 3 :
- ,
или, что более эффективно,
- ,
и проверив его в полиномиальном представлении:
- .
Смотрите также
- Гауссовский логарифм
- Ирландский логарифм , подобный метод, полученный эмпирически Перси Ладгейтом.
- Конечная арифметика поля
- Таблица логарифмов
Рекомендации
- ^ Зех, Юлий Август Кристоф (1849). Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из собрания Vega-Hülße) 1-е изд.). Лейпциг: Weidmann'sche Buchhandlung . Архивировано 14 июля 2018 года . Проверено 14 июля 2018 . Также входит в состав: Фрайхер фон Вега, Георг (1849). Хюльсе, Юлий Амброзиус ; Зах, Юлий Август Кристоф (ред.). Sammlung Mathematischer Tafeln (на немецком языке) (Полностью переработанная ред.). Лейпциг: Weidmann'sche Buchhandlung . Bibcode : 1849smt..book ..... V . Архивировано 14 июля 2018 года . Проверено 14 июля 2018 .
- ^ Зах, Юлий Август Кристоф (1863) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из собрания Вега-Хюльсе), 2-е изд.). Берлин: Weidmann'sche Buchhandlung . Архивировано 14 июля 2018 года . Проверено 13 июля 2018 .
- ^ Зах, Юлий Август Кристоф (1892) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из собрания Вега-Хюльсе), 3-е изд.). Берлин: Weidmann'sche Buchhandlung . Архивировано 14 июля 2018 года . Проверено 13 июля 2018 .
- ^ Зах, Юлий Август Кристоф (1910) [1849]. Tafeln der Additions- und Subtractions-Logarithmen für sieben Stellen (на немецком языке) (Специально перепечатано (из собрания Вега-Хюльсе), 4-е изд.). Берлин: Weidmann'sche Buchhandlung . Архивировано 14 июля 2018 года . Проверено 13 июля 2018 .
- ^ Лидл, Рудольф; Нидеррайтер, Харальд (1997). Конечные поля (2-е изд.). Издательство Кембриджского университета . ISBN 978-0-521-39231-0.
- ^ Якоби, Карл Густав Якоб (1846). "Über die Kreistheilung und ihre Anwendung auf die Zahlentheorie" . Journal für die reine und angewandte Mathematik (на немецком языке). 1846 (30): 166–182. DOI : 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). Черчхаус, Роберт Ф .; Герц, Ж.-К. (ред.). «Таблица некоторой информации о конечных полях». Компьютеры в математических исследованиях . Амстердам: Издательство Северной Голландии : 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 .