Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
соотношения линейной зависимости в нормированной форме (т. е. с
коэффициентом 1 при к (x)m) и являются коэффициентами многочлена G. При
этом мы знаем, что для нахождения этого соотношения линейной зависимости
требуется рассмотреть лишь степени многочлена h (х) не выше &-й, где
число k можно получить из алгоритма Берлекэмпа. Элементами множества С
являются корни многочлена G, лежащие в поле Fg, и только они. Этот метод,
сводящий проблему нахождения элементов множества С к задаче отыскания
корней некоторого многочлена в поле Fg, носит название алгоритма
Цассенхауза.
4.9. Пример. Рассмотрим снова тот же многочлен / (х) - = хв - Зх5 +
5х4 - 9х3 - 5х2 + 6х + 7 С Fa3* ЬД, что и в примере 4.7. С
помощью алгоритма Берлекэмпа мы уже нашли число
его неприводимых сомножителей k, равное 3, и /-разлагающий многочлен к
(х) = х3 + 2х2 + 4х ? f23 [х ]. Применим теперь алгоритм Цассенхауза для
нахождения множества С тех элементов с € Fa3, для которых НОД (/ (х), к
(х) - с) Ф I. Мы имеем
к (х) щ х3 + 2х2 + 4х (mod / (х)),
к (х)2 = 7Х5 + 7х4 + 2х3 - 2х2 - 6х - 7 (mod / (х)),
так что ясно, что к (х)2 не зависит линейно от 1 и к (х). Поскольку число
т элементов множества С не превосходит к - 3, то степень к (х)3 должна
быть наименьшей степенью многочлена к (х), которая линейно зависит от
предыдущих степеней. Имеем
к (х)3 = -11х5 - Их4 - х3 - 9х2 - 5х - 2 (mod / (х)),
и искомая линейная зависимость такова:
к (х)3 - 5h (х)2 + 11 к{х) - 10 = 0 (mod / (х)),
следовательно, G {у) = у3 - 5г/2 + Му - 10. Теперь, применяя либо методы
следующего параграфа, либо метод проб и ошибок, находим, что корнями
многочлена G в поле F23 являются элементы 2, -3 и 6. Каноническое
разложение многочлена / в F23 Ы находится так же, как в последней части
примера 4.7. ?
Приведем еще один метод, который основан на применении матриц из
многочленов. Хоть его схема более сложна, но зато он представляет больший
теоретический интерес. Под матрицей из многочленов мы будем понимать
матрицу, элементами которой являются многочлены из кольца Fg [х ].
4.10. Определение. Квадратную матрицу из многочленов будем называть
невырожденной, если ее определителем является ненулевой многочлен, и
унимодулярной, если ее определителем является ненулевой элемент поля fr
206
Гл, 4, Разложение многочленов на множители
4.П, Определение. Квадратные матрицы из многочленов и Q будем называть
эквивалентными, если существуют унимодулярная матрица из многочленов V и
невырожден матрица Е с элементами из поля Fg, что Р = UQE.
\\Lf?
•-Л • Х>:.
\Аь
У#
а!
-Uv
о*
Легко проверить, что введенное нами понятие эквивалента матриц из
многочленов действительно является отношением эк валентности в том
смысле, что оно рефлексивно, симметричнд транзитнвио.
Мы видели в § 1. что существуют многочлены /и,
€ Fg 1Х), О < deg (hi) < deg (/), t = 2, А, которые вм с (.х) • I
являются линейно независимыми иад полем Fg
шениями сравнения hq = h (mod /). Ясно, что многочлены можно выбрать
нормированными. Следующая теорема являет| основополагающей.
4.12. Теорема. Пусть f - /д ... fh, где /1; ..., fk -нормированные
неприводимые многочлены из fg UJ
•AS:
h
hk С IFg be 1 - нормированные многочлены
разлищ и
стеi
2? ¦ 4 м ^ ц <? "
<deg (/}, которые вместе с --- 1 являются линейно независим над полем'fq
решениями сравнения hq = h (mod/). Тогда ди нальная матрица из
многочленов
;#
.:л
?>
0' о
¦"
I(r)
о о
у *
!
h
¦ X#
• ' щ -• ivl
.
:• • у
Ш
эквивалентна матрице из многочленов
•ш
: . У:
f 0 0 . . . 0
0 . . . 0
л 0 - -1 ... 0
¦ ¦ hk * * 0 " * ш ¦ у у 0 . . . у ¦ 1
•1! а
. V.
1 >
• JC
Г"$
'>.¦#
\'Ъ>
'Лу
№
'
• у/.
I
X
•>|Я?
"I
%
М
т
Доказательство. Из рассуждения, следующего из (4.3), в кает, что
существуют элементы ец С Fg, такие, что hi (х) = etj (mod fj (л)), 1 < i,
j < k. Обозначим k X А-матрицу через E. Покажем, что матрица Е
невырожденна. Если бы было не так, то существовали бы такие элементы dlt
4 € ие все равные нулю, что
3"
м
ш
:М ¦
§ 2. Разложение многочленов над большими конечными полями 207
Эго означало бы, что
к
? dthi = 0 (modfj), / = 1 к,
i-i
к
откуда следовало бы, что 2 = О (m0(3 D- Но так как deg (А*)<
(=1
< deg (f) для всех iy 1 < i < k, то на самом деле мы получи л н бы
k
равенство 2 djii = 0, которое противоречит линейной незави-
1 = 1
симости многочленов къ hk.
Теперь заметим, что ЛЕ является невырожденной матрицей из многочленов,
так как det (Л?) = (-1 )k~lf det (?). Поэтому мы можем написать D - (D
(ЛЕ)-1) ЛЕ, и теорема будет доказана, как только мы покажем, что U - D
(ЛЕ)"1 является унимодуляр-ной матрицей из многочленов.
Пусть ЛЕ - (Ьи), где Ьц ? Fg Ы. Тогда, так как hx ~ 1, то = fexj = f = 0
(mod fs) для 1 < / < к, а для 2 < i < к имеем bu = htexs - е^ ~ h} - ец н
0 (mod fs) при 1 < j < к, так что
bu = O(mod^) для всех 1 < i, j < к, (4.15)
Далее,
(Л?) 1 = jt'k - ^et (Е) f /<а"
где Bji - алгебраическое дополнение элемента матрицы ЛЕ, так что
