Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Тогда
/,(*<)=(-1 )"*"+" П /(в х),
/=1
где <оь щ - корни степени t из единицы над Fg с учетом их кратности.
Доказательство. Пусть а - аь а2, ат - все корни многочлена /. Тогда af,
ат - корни многочлена ft с учетом их кратности. Поэтому
132
Гд, 3, Многочлены над конечными полями
Щ
<т
• N iTfrSVi11 • "i S М&Л№Л№ЛЗ-Ь№*&М&+№Мег?-№-(tm)±*/^Ч*^,чл,^,льл1?.гъ-
>^?чг*-тчпрняч*лн-+Фт1*ше^?ы*9ъ*ЛФ\,и+.ггчп-й?УНЪ1ш1,г2-'гя-гг*,я-тя-у.ыя
н -.'.те**
Сравнивая коэффициенты в равенстве
ш
ж
х* -----
П (х - схф
i-i
jf
полуааем, что II со, - (
¦¦¦¦¦¦¦¦ j -¦¦¦¦¦¦-¦• •
1
так что
?<8 .<! :*
/
г.,"*
? m
;1
Р*1 ?
М*
f
<* н> П ГГ (а>у1* - а,') ¦¦"¦-
/=Д ь=1 г
=: J) m<* + l) fj - /- 1V"<-'-M
"1
/
п
* %
?!
4
¦ ж
ш
поскольку coi , ..., &>/ пробегают в точности все корни степени f\ из
единицы над |ф. ?
3,40, Пример, Рассмотрим неприводимый многочлен / (х) = х$ _|_ х д..
] (- р, [х]. Чтобы вычислить /3, заметим, что корни J
третьей степени из единицы над Fg суть 1, о) и (c)4 где <о ¦¦-
корень .J
многочлена х2 + х. 4 I, принадлежащий полю Fd- Тогда
/3 (д3) - (--!)" / (х) [ (шх) / {А) =
- (л4 Д~ х 4- 1) (шх4 4- (ах 4 1} (<444 т- нгх 4 I) =
.1
х
I- Xе
.8
так что 4 (х) - х
4 Д..
X
4. yS J...
•ii
X
Дру гой с п ос о б о ты скан и я характеристического м *1. о го ч л ена
элемента о4 базируется на теории матриц. Пусть / (х) - хт
т -I
л -
о
о
ап> и пусть А' - сопровождающая
ляемая как т X т- матрица вида
0 . . - 0 (Ц
0 . . .¦ 0 4
1 . . . 0 Л О.* 4* rt <%
¦а fr V а •fr 0 ... ь ь % * 1
•"
\Ц
Тогда f является характеристическим многочленом матрицы А в смысле
линейной алгебры, т, е. / (х) - det (х/ Л), где /
единичная m X m-матрица над fq. Для каждого t (- М мнопф! член ft
является .характеристическим многочленом для Тй ст ни Аг матрицы А, Так,
вычисляя степени матрицы Л, можн получить многочлены/V
3.41. Пример. Интересно выяснить, какие из многочлене^
ft являются неприводимыми в кольце fg [хЗ
рассуждения;
§ 3. Построение неприводимых многочленов
133
предшествующего теореме 3.39, сразу следует, что характеристический
многочлен ft элемента а* ? fqm иад будет неприводим 15 f q lx 3 тогда и
только тогда, когда он совпадает с минимальным многочленом gt элемента а*
над lFg, т. е. когда deg (gt) = m, а для этого необходимо и достаточно,
чтобы т было показателем, которому принадлежит q по модулю d = е/НОД (/,
е). Рассмотрим, например, случай q - 2, т - 6, е = 63. Так как
показатель, которому принадлежит число q по модулю какого-нибудь делителя
числа е, должен быть делителем числа т, то кроме т возможны лишь
показатели k - 1, 2, 3. Для них ф - 1 = 1, 3, 7, так что сравнения qk я 1
(mod d) выполняются лишь при d = = I, 3, 7. Таким образом, многочлен ft
приводим в кольце Fa Сх I как раз в случаях, когда НОД (t, 63) = 9, 21,
63. Поскольку достаточно рассмотреть лишь значения if, удовлетворяющие
условию 1 < /^<63, то получаем, что многочлен ft неприводим в кольце EF2
[х] для всех значений t из указанного интервала, за
исключением t = 9, 18, 21, 27, 36, 42, 45, 54, 63. ?
На практике неприводимые многочлены часто появляются как минимальные
многочлены элементов какого-нибудь расширения исходного поля. Если в
проведенном выше рассуждении в качестве f взять примитивный многочлен над
Fg, т. е. считать, что е = qm - 1, то степени элемента а будут пробегать
все ненулевые элементы поля F$m. Поэтому описанный выше метод можно
применять для вычисления минимальных многочленов над всех элементов
мультипликативной группы F^ поля F^m.
Прямой метод нахождения минимальных многочленов состоит в следующем.
Пусть 8 - образующий элемент поля fgm как простого расширения поля F?>
так что {1, 9, 0т~!} - ба-
зис F^m как векторного пространства над Fr Чтобы найтн минимальный
многочлен g элемента р ? F*m над выразим степени р°, р1, ..., рт через
базисные элементы. Пусть для < т -f- 1
т
р-i = ? bifii-1.
1^)
Запишем многочлен g в виде g (х) - стхт + ... + схх + ?<>* ^ам нужно,
чтобы g был нормированным многочленом наименьшей степени, удовлетворяющим
условию g (Р) = 0. Это условие g (Р) = cmpm + ... -f схр + с9 - 0
приводит к однородной системе линейных уравнений
/n-j-i
? = о, /= 1, 2, т, (ЗЛО)
1=1
с неизвестными с0, еь ст. Пусть В - матрица коэффициентов этой системы,
т. е. некоторая (т -f- 1) X m-матрица В - (Ьц)г
134
Гл. 3. Многочлены над шнечными полями
' ¦ ¦ ¦-•¦ ¦ ¦•-•-•-•. ^-. У ¦ ¦ ¦ - ¦¦.¦.[- ¦^- •-1 -iVfl j
у ¦ ¦ -ГГГГГнМУг"-^ " v ¦ fc'-'-~ p ц-~-'1 ¦-¦
L-fr4 C"^W^wVJ"*>K- H -X-X-W L-X-> HAW-X-Xfrl Р**чЧ f-
XhTOri|'rt'r""Vl .h/Vr Kl НШСА?Ш
и пусть ее ранг равен г" Тогда размерность пространства решений.! системы
(ЗЛО) равна а -¦¦¦¦ т то I - М и поскольку 1 лС г ¦< #vj то 1 ¦< s •< т.
Поэтому мы можем произвольно задать значения! для s из т Л- I неизвестных
c0t сг, ..., cmi и тогда остальные не-известные определятся однозначно.
Если s -¦¦¦- 1, мы положим ст 1, а если $ > L то положим сш- суп",л - ...
~ cmi_s+2 =¦
