Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
ft из поля разложений J этого многочлена над В силу теоремы 2.23 (iii)
существуй#^ многочлен gr С fq ^х], 'такой, что deg (g,) < deg (Д) и
FT/yjy (gt (0i)) ----- 1.
is;
Г. w*"
№
N
*) Так как НОД
\ n± ¦ ¦ nk
2) Учитывая, что Fx -= SF^ (00.
~ 1. - Прим. перев. Прим. перев.
§ 1. Разложение многочленов над малыми конечными полями 195
Ввиду того что k > 2 (по предположению), мы можем применить китайскую
теорему об остатках и получить такой многочлен g ? F<* 1*3 степени меньше
пл что
g = gi (mod /j), g = 0 (mod /,). (4.9)
Из (4.8) и (4.9) следует, что
' (? №)) = ** так что из теорем 2.23(iv) и 2.26 получаем равенство
т rFffq (g (0l)) = JV/n,,
где f - поле разложения многочлена / иад Fg. Из определений следа и
элемента 9Х вытекает, что
Т (g (х)) = Ы!пг (mod (х)),
Однако второе сравнение в (4.9) приводит к сравнению Т (g(х)) = ы 0 (mod
/2 (х)), и, поскольку число N(nt как элемент поля F^ отлично от нуля, мы
получаем противоречие с (4.7). Это противоречие означает, что по крайней
мере одни из многочленов Tif 1 < г < п - 1, является /-разлагающим. ?
4.4. Пример. Разложим многочлен
/ (х) = X17 + ХИ -f X13 -j- X12 Д- X11 Д- X10 Д Xs Д-
-|~х8-рх7-рх5-рх4-у-х-р1 ?F2 М"
Поскольку НОД (/ (х), /' (х)) - х10 Д- х8 + 1, то многочлен /о (*) = /
(х)/НОД (/ (х), /' (х)) = х7 + х6 + х4 + х Д 1 не имеет кратных
сомножителей. Разложим/0 (х) описанным выше методом, найдя /0-разлагающий
многочлен. Для этого будем приводить по модулю /0 (х) степени х, х2, х4,
х8, пока не найдем наименьшего натурального числа N, такого, что x*N = х
(mod /0 (х)).
rt-1
Для упрощения записи условимся многочлен 2 atx1 обозначать
{-О
п-набором (вектором) (aQ, аъ ап^) из его коэффициентов; в частности, /0
(х) = (1, 1, 0, 0, 1,1, 0, 1). Подсчет нужных степеней переменной х по
модулю /0 (х) упрощается, если заметить, что квадрат многочлена (og, alt
Од) по модулю /0 (х) совпадает (в векторной записи) с произведением
вектора (а0> аъ а") на квадратную матрицу порядка 7, образованную четными
степенями переменной х, а именно х°, х2, х12, приведенными по мо-
дулю /0 (х). Эта матрица получается из правых частей следующих сравнений
(по модулю /0 (х)):
х° = (1, 0, 0, 0, 0, 0, 0), х2 = (0, 0, 1, 0, 0, 0, 0);
13*
196
Гл. 4. Разложение многочленов на множители
X4 = = (0. 0, 0, 0, 1, 0, 0),
Xе Z = (0, 0, 0, 0, 0, 0, 1),
X8 = = (0, 1, 1, 0, 0, 1, 1).
ххо = = (1, 0, 1, 1, 0, 0, 1),
X12 ~ " (0, 1, 0, 0, 1, 0, 1).
• t.t .
ъЛ,
Произведя теперь с помощью этой матрицы последовательные
. f+Я.
. **> Й
л* "X.
• /*
•- • ?
, получим (по модулю f oW)
X = (0, 1, 0, 0, 0, 0, 0),
X2 = (0, 0, 1, 0, 0, 0, 0).
X4 -= (0, 0, 0, 0, 1, 0, 0),
Xs = (0, 1, 1, 0, 0, 1, 1).
X16 ^ (1, 1, 0, 1, 0, 0, 0),
X32 ~ (1, 0, 1, 0, 0, 0, 1).
Xе4 = (1. 1, 0, 0, 0, 0, 1)>
X128 = о, 1, 1, 0, 1. 0, 1),
хш = (1, 0, 0, 0, 0, 1, 0),
- (0. 0, 1, 1, 0, 0, 1).
хш4 = Рд 1, 0, 0, 0, 0, 0).
¦Я
* ** \*
. а-,
.у*': >
• <>'
. •'vTvr^
:#
i'v:
' #
. *<Ч v . •• ч*Л
\А>)г
¦ 'А > * •••
:• v^-
*mys .
•;"Ч
Таким образом, N - 10 и многочлен Т имеет вид
§
Т (х) = 7\ (х) == S ^ = (1> Ь 1, 0, 0, 0, l)(tnod /ой)"
/-о
Поскольку многочлен 7\ (х) не сравним с константой по /о (#), то он
является /уразлагающим многочленом. НОД (/о (*), 7\ (*) " с) Для значений
с = О и с - 1:
'.й
НОД (/" (*), Г, (х))
НОД (/" (*), Г, (дс) - 1)
= НОД ((1, 1. О, О, 1, 1, О, 1). (1, 1, 1, О, О, О, 1)) =
= хь + xi + je* + Xs + 1,
- НОД<(1, 1, О, О, 1, 1, О, 1), (О, 1, 1, О, О, О, I)) =
= хг + х + 1,
'Чу?*
Ш
¦А.
9 (%
,у>
•¦Ля5
s jA .
5 Р
'4v
Hi
а по формуле (4.2) получаем
/о (x) - (x& -f x4 -f x3 + я2 + 1) (x2 + x -f 1).
Второй сомножитель, очевидно, неприводим в Fs [х]. Посколь1 число N = 10
является наименьшим общим кратным степеГ
§ 1. Разложение многочленов над малыми конечными полями 197
неприводимых делителей многочлена /0 (х), а любое нетривиальное
разложение первого сомножителя привело бы к значению N, отличному от 10,
то первый сомножитель тоже неприводим в F2 (х).
* Теперь остается разложить многочлен НОД (/ (х)} /' (х)) = сг: х10 + х8
4" I. Нетрудно заметить, что х10 4- х8 4- 1 ~ (х5 + 4 х4 ~г I)2" причем
многочлен хь + х4 + 1 делится на неприводимый делитель x2-fx+l многочлена
/0 (х), так что х5 + х4 + 4 1 - (х3+ хф J) (х2 4- х 4- 1), где многочлен
х8 + х 4- 1 тоже неприводим над Fg fxl. Окончательно получим такое
каноническое разложение многочлена / (х) в F2 Ы:
/ (х) - (х5 4- х4 + х3 4- х2 4- 1) (х3 + х 4- I)2 (х2 4- х 4- I)8. ?
Следует, однако, заметить, что, вообще говоря, /-разлагающие многочлены
вида Tt могут не привести к полному разложению многочлена /, поскольку
они неспособны отделить те неприводимые делители многочлена /, для
которых число Nfttj делится на характеристику поля fg. В таком случае
обычно сначала с помощью /-разлагающего многочлена 74 находят частичное
нетривиальное разложение многочлена /, а потом ищут новые 74 для каждого
из полученных сомножителей. Так в конечном счете получают полное
