Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
аппарат для решения этой проблемы будет развит в следующ параграфе.
4.7. Пример. Разложим многочлен / (х) = х* - Зхъ + бх4
- 9х3 - 5х2 + 6х + 7 над полем Так как НОД (/ (х), [* (х))
- 1, то многочлен f (х) не имеет кратных сомножителей. Пр няя алгоритм
Берлекэмпа, найдем степени х231' по модулю f для i 0, 1, •••, 5. Это
приводит к 6 X 6-матрнце
•• Щ
¦Ч
в
так что матрица В
В-I
1 0 0 0 0 0
5 0 1 8 - 3 - 10
10 10 10 0 1 -9
0 9 - 8 10 11 *
11 0 -4 7 7 2
-3 0 10 9 2 "9
- / имеет вид
• 0 0 0 0 0 0
5 - -1 - 1 8 3 -10
10 10 9 0 1 -9
0 7 9 - 9 10 - -11
и 0 4 7 6 2
ь 3 0 - -10 9 2 10
. • Ui'
•ч
¦ зщ
¦ T-fi
• V:
•/'I*
'I'S*'
щ
fS&ii } ?*<•
. ^/а
к Ч .'-Г:
.4%
• хс-л
Sty
XI
:•* U-! '/¦S
!
*!" * S .! U
,iv * 0*
• /•
Tr
v<X?!
'X
"<
•ч
a
№
Приведение этой матрицы элементарными преобразованиями стол* цов к
ступенчатому виду показывает, что ранг г матрицы В равен 3, так что
многочлен / имеет к ~ 6 - г -= 3 различны, нормированных неприводимых
сомножителей над полем Fts. Баз! пространства решений однородной системы
(4.6), соответствующ^ матрице В - /, задается векторами = (1, 0, 0, 0, 0,
0), h& ?
(0, 4,2, 1, 0, 0) и&з - (0, -2, 9, 0, 1, 1), которыесоответст многочленам
кг (х) = 1, Ла (х) -- Xs + 2хЙ ф 4х и h2 (х) = **
§ 2. Разложение многочленов над большими конечными полями 203
х4 + 9xz - 2х. Возьмем теперь /-разлагающий многочлен h2 (х)
и рассмотрим многочлен от у
F &) = Я (*)• М - у)
1
О
0
1
о
о
о
о
3
1
0 2
1 О
Б
-3
1
4
2
1
9
5
-3
У
4
2
1
¦5
9
5
О
У
4
6
¦5
9
О
О
¦У
О о
ООО
7
6
-5
О
О
О
У
о
7
6
О
о
о
о
о
7
о
о
о
1
2
О О
¦у О
О О О О О ' 1
У
Этот определитель можно вычислить непосредственно, н мы получим F {у) =
tf + 4у5 4- 3у4, - 1уг + 10у* + Му + 7, Поскольку многочлен / имеет три
различных нормированных неприводимых сомножителя в кольце f28 [ж],
то, как отмечалось выше, многочлен F (у) может иметь не более трех
корней в поле F28. Применяя
либо один из методов, рассматриваемых в следующем параграфе, либо метод
проб и ошибок, находим эти корни, равные соответственно 2, -3 и 6. Далее,
НОД (/ (х), h2 (я) - 2) = х* - х + 7,
НОД (/(*), ft8(*) + 3) = *-4,
НОД (/ (х), h2 (х) - 6) = х3 + 2х2 + 4х - 6,
так что каноническим разложением многочлена / (х) в кольце
iT'
з
lx] является
/ (х) = (х - 4) (х2 - х + 7) (х3 + 2Х2 + 4х - 6). ?
Другой метод характеризации тех элементов с поля Fg, для которых нужно
подсчитывать НОД (/ (х), h (х) - с) в формуле
(4,2), основан иа следующих соображениях. Пусть сохранены те же
обозначения, что и выше, и пусть С обозначает множество всех тех с ? fqt
для которых НОД (/(х), h (х) - с) ф 1. Тогда из (4.2) следует, что
/(*) = П НОД (/(*), h(x) -с),
с € с
(4.14)
Так что многочлен / (х) делит произведение П (ft (х) - с).
введем в рассмотрение многочлен
- П(,
с 6 С
ес
G(y)
с).
204
Гл. 4. Разложение многочленов на множители
Тогда многочлен / (х) делит G (h (х)), и многочлен G (у) можно
охарактеризовать следующим образом.
4.8. Теорема. Среди всех многочленов g С Fg hj\, таких, что / (х) делит
g (h (х)) , многочлен G (у) однозначно определяется тем, что это
нормированный многочлен наименьшей степени.
Доказательство. Мы уже показал и, что нормированный многочлен G (у)
обладает тем свойством, что / (.х) делит G (h (я)}. Легко видеть, что
многочлены# ? hjh такие, что / (х) делит g (h (x))f образуют ненулевой
идеал кольца Fg [у]. По теореме 1.54 этот идеал является главным идеалом,
порожденным некоторым однозначно определенным нормированным многочленом
G0 ? Fg Это значит, что многочлен G0 (у) делнт G (у), так что
с" (У) П (У-с)
для некоторого подмножества Сх множества С. Следовательно, / (х) делит G0
(h (х)) - П (h (х) - с), и, значит,
с € Ci
/ (х) = п НОД (/ (х), h (х) - с).
с Gc,
Сравнение с (4.14) показывает, что Сх ~ С. Поэтому G0 {у) - ~ О {у)> и
теорема доказана. ?
Этот результат можно использовать следующим образом. Пусть т - число
элементов множества С. Тогда запишем
М
G (у) = п (у-с)
dc
т
? Ь/у1
1=о
с коэффициентами bj ? F4. Поскольку / (х) делит G (h (х)}, то мы получаем
т
2] bjh(xY = 0 (mod/(x)).
/=о
Так как bm = 1, то это сравнение можно рассматривать как нетривиальное
соотношение линейной зависимости над полем Fg> связывающее вычеты по
модулю / (х) многочленов 1, h (х), h (х)2, h (х)т. Согласно теореме 4.8,
если произвести нормирование так, чтобы bm ~ 1, то такое соотношение
линейной зависимости определяется однозначно; поэтому вычеты по модулю /
(х) многочленов 1, h (х), h (х)2, ,h (x)m~* линейно независимы над Fq.
Ограничение т < k (где k определено в начале параграфа) вытекает из
(4.14),
Поэтому многочлен G можно найти, если приводить по модулю / (х) степени
многочлена h (х): 1, h (х), h (х)2, пока не найдем
§ 2. Разложение многочленов над большими конечными полями 205
ту наименьшую степень к (х)т этого многочлена, которая линейно зависит
(над полем Fg) от предыдущих степеней. Коэффициенты этого первого
