Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
обладает тем свойством, что ее минимальный многочлен совпадает с ее
характера стнческим многочленом. Пусть минимальный многочлен матрицы А
имеет
р (х)г, где р (х) --нормированный неприводимый многочлен иад нолем F#*|f
deg (р (х)) d. Не пользуясь теоремой 9.96. доказать, что цикловая суммШ(r)1
ЛМС Ж задается формулой, приведенной в этой теореме.
9.72. Найти цикловую сумму ЛМС Ж над полем F3, onреде/генной в при*уц
мере 9.91.
9.73. Доказать теорему 9.98.
w
щ
х
Щ
t
М
ж
::мШ
Ш
Ш
Глава 10 Т аблицы
В этой главе собраны некоторые таблицы, облегчающие вычисления в конечных
полях, а также таблицы неприводимых и примитивных многочленов над
конечными полями. Описание этих таблиц приводится соответственно в § i и
2.
§ 1. Вычисления в конечных полях
Операции умножения и деления ненулевых элементов поля Fg можно выполнять,
пользуясь аналогом понятия логарифма. При этом вместо термина "логарифм"
нам будет предпочтигельнее пользоваться термином "индекс". Если b -
примитивный элемент поля то для любого элемента а ? Fg существует
единственное целое число г, 0 ф г < q - 1, такое, что а = Ьг. Это
число г
называется индексом элемента а (по основанию Ь) и обозначается через ind6
(а) (или просто ind (а), если элемент b фиксирован). Индекс как функция
(будем называть ее индексной функцией) удовлетворяет следующим основным
условиям:
ind (ас) se ind (а) + ind (с) (mod (q - 1)), ind (ac~l) = ind (a) - ind
(c) (mod (q - 1)).
Функция, обратная к индексной функции и соответствующая взятию
антилогарифма, называется экспоненциальной функцией и обозначается через
ехр^ или просто ехр. При этом выполняются
соотношения
exp (г) = br, exp (ind (a)) a, ind (ехр (г)) = /*.
Имея таблицу функций ind и ехр для поля Fq, можно легко выполнять все
четыре действия в поле Fq - сложение, вычитание, умножение н деление. Для
выполнения сложения и вычитания в поле Fq это поле удобно рассматривать
как векторное пространство над его простым подполем Fp', для выполнения
умножения и деления в поле Fq используются свойства функции ind, а
таблица функций ехр и ind позволяет переходить от одних обозначений к
другим. В табл. А приводится полный список ненулевых элементов и
соответствующих им индексов для всех конечных полей Fq, где q - составное
число, не превосходящее 128. В ко-
668
Гл, 10. Таблицы
лонке, соответствующей значениям функции ехр, скобки и тые, обычно
используемые для записи вектора, соответствующе заданному элементу
а = (аь ..., ап) - агЬп~1 4 афп¦
а
о < а( <р*
•
AS
'VW
'•>4 К*
поля f(p где q = рл, будут опускаться.
10.1. Пример. В качестве примера использования таблицы Ц вычислим в поле
0% выражение
l(b + I) + (2Ь + 2) 6] (6 + 2)-1 h Ь.
Используя ту часть табл. А, которая соответствует полю получаем
ind ((26 +2) Ь) ~ ind (26 4 2) 4 ind (Ь) = 3+1 =
= 4 (mod 8),
Щ
(26 4 2) 6 = exp (4) - 2.
Тогда (6 4 1) f (26 ind ([(6 + 1) + (26 -
2) 6 = 6 и 2) 6] (6 + 2)"1) - ind (6)
-1-6
- ind (6 4 3 (mod 8), 26 + 2.
•i .> -4#
• *. vW
. * - *^.УУ > '<>t( 45.
.. ^ vT
'• ll'S
"> ;Й
• &Н'-'
•v>$&
[(6 +1)4 (26 4 2) 6J (6 4 2)-1 - exp (3) =
Таким образом, исходное выражение равно (26 4 2) 4 &-Й - 2.
Таблица В предоставляет другую возможность для выполнен арифметических
операций в конечных полях. Первые две ее лонки представляют собой таблицы
логарифмов Якоби L (п) полей (F4, где 2<^<6 (определение логарифма Якоби
в упр. 2.8). Символ п -¦> s здесь означает, что L (п) = s тельно
некоторого фиксированного примитивного элемента В случае когда
характеристика поля равна 2, величина ? | является неопределенной.
Перемножение элементов Ьп про водится обычным образом, т. е. Ьт-Ьп - Ьт+п
сложение же #Г производится по правилу
fym ..j," jfyn (п-т)
(указанному в упр. 2.8). Символ 4, расположенный перед чиной л, здесь
указывает на то, что элемент Ьп является митивным.
10.2. Пример. Используя табл. В, вычислим выражение
(6е 4 Ъ%ъ 4 641) (I 4 635)-1 4 628
поле Fg** Получаем: 6е 4 62г> - &6+z.(i9> __ ?49 и ^ ^ щ
640+М4> = 672. Так как 1 4 635 - 6х* <35> = 631, то
(Ь" + ^ 4 644) (I 4 636)"1 - 6726'31 = 641
?:х
т
t :>s
•48
Б
¦' fe
ш
' i I ^
f
•-<4
¦щ - -1$
.
¦М
§ 1. Вычисления в конечных полях
669
Далее, поскольку и аргумент функции L, и показатель степени элемента b
рассматриваются по модулю 63, то
?41 ?28 ?41+/, (-13) _ ?41+/. (50) = ?101 _ ?38(
что и является искомым результатом. Заметим, что полученный элемент Ь88
является примитивным элементом поля Р64. ?
В остальной части табл. В приводятся сведения о минимальных и
характеристических многочленах, а также о дуальных базисах. Рассмотрим в
качестве примера две следующие строки из таблицы для поля Рв4 над полем
FV
+ 20 ^ 26 [100001 ] 26 6 49 29 9 46 : 19
21 42 [1010П] [И]
Символ \аха2 ... ат3 означает, что многочлен вида хт + аххт-1 + а2хт~~2 +
... + ат является характеристическим многочленом данного элемента
относительно данного расширения поля. Так, Xй + х6 + I является
