Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
степень (ср. с материалом, предшествующим теор 2.23). Поэтому многочлены
Ft (х) являются неприводимыми множителями многочлена F (х) в кольце fp
[х], но некоторые них, вообще говоря, могут совпадать между собой.
Значит, к
U3 име*
.т
::т
т
.
р
(4.
ионическое разложение многочлена F (х) в кольце F вид
F (х) - Gi (х) . . . Gr (х),
где Gf (х), i с t < г, - степени различных неприводимых ми(c) членов Fx
(х). Это каноническое разложение может быть полу" с помощью одного из
алгоритмов, изложенных в § 2 этой
&
§ 3. Вычисление корней многочленов
Поскольку многочлен / (х ) = /0 (х) делит F(x), то из (4.31) следует, что
/(*) = П НОД (/ (х), G,(JC)). (4.32)
/ j
формула (4.32), как правило, дает нетривиальное частичное разложение
многочлена f (х). Тривиальным оно является в том и только том случае,
когда НОД (/ (х), Gt (х)) ~ f (х) для какого-
нибудь /, 1 с / < г, что эквивалентно условию г = 1 *), и
тогда
/ (х) делит Fi (х). Сравнение степеней показывает2), что п <dt - т. Кроме
того, корни многочлена f(x) в этом случае все сопряжены относительно поля
IF,,. Таким образом, мы можем записать (изменив, если нужно, нумерацию
корней многочлена / (х))
у. = yf\ 1 < f < я, где 0 = < Ъг < ... <,Ьп<,т.
Положим Ьп+1 - т и d - min (/?i+1 - bt). Ясно, что d < min.
Могут встретиться следующие две возможности:
(A) ^+i - bt > d для некоторого 1 < / < п;
(B) bi+l - bt = d для всех (, 1 с / < л.
В случае (А) заметим, что множеством корней многочлена / (х) является
а множеством корней многочлена fd (х) является
(V1+i, ^............... Yf""+T
Из условия (А) следует, что эти два множества корней не совпадают. Но, с
другой стороны, поскольку bi+l - bt = d для некоторого г, 1 ^ i ^ л, эти
два множества корней содержат общий элемент. Таким образом, многочлен НОД
(/ (х), fd (*)) отличен как от f (х), так и от 1. Следовательно, НОД (/
(х), fd (х)) является нетривиальным делителем многочлена / (х). Нетрудно
видеть также, что в этом случае d < т/п.
В случае (В) сравнение множеств корней многочленов f (х) н fd(x)
показывает, что / (х) == fd (х), так что НОД(/(х), (х)) - 1 для всех k -
1, d - 1. Кроме того, d = min, так что число п делит т, и, значит, bt = d
(i - 1) для i - 1, п.
Отсюда следуют равенства, у* = у? l\ i = 1, 2, . . n,
x) Так как если G* (jk) = Fi (x) to F( является минимальным многочленом
каждого корня у, многочлена /. - Прим. перев.
2) Так как Fi содержит все у;-, I < / < п. Если бы было d1<m> то все
V/ принадлежали бы IF что противоречит выбору q - рт.-Прим. перев.
222
Гл. 4, Разложение многочленов на множители
• I :!?
№
т. е. элементами yt являются элементы, сопряженные с ух отнй тельно поля
F </, и только они. Следовательно, f (х) явля
минимальным многочленом элемента у, над F d и, значит,
приводим "ад Ги.
Поэтому в соответствии со случаями (А) и (В) мы получ следующие две
возможности:
(A) Многочлен НОД (/ (х), fh (х)) для некоторого k, I < if < min,
является нетривиальным делителем многочлена
(B) НОД (J (х), fk (х)) = I для всех k = 1, d - 1, d ^ min С IN, и f (х)
= fd (х) - минимальный многочлен мента уг над полем
Следовательно, в случае (А) наша цель отыскания нетрц ального делителя
многочлена f (х) достигнута. ¦;
В случае же (В) еще требуется дополнительное исследовая|| Пусть р снова
обозначает образующий элемент поля F? над Тогда РрЛр) = F? - f mt так что
элемент р имеет степень mid
над полем F^ В частности, это означает, что p^F^ для всеж|
1 </<п - 1. Пусть теперь коэффициенты ctj многочлена таковы, что а^0 Ф 0
для некоторого /0, 1 <; /0 < п - 1. трим многочлен
4*5
У,'
¦ У. н
1 (х) = Г7 (М,
(4.
который является нормированным многочленом степени п над
Так как р^,{1 ф FpCn a a,h?Y*pd, то, значит, коэффициент
х/е в многочлене f (х) не принадлежит полю Fpa- Поэтому f
не является многочленом над полем fи, следовательно, щ
указанную выше процедуру применить к многочлену f (х), случай (В) не
может встретиться, и мы получим некоторый тривиальный делитель многочлена
f (х). А поскольку f (х)
- рnf (р-'х), то каждому нетривиальному делителю многочлй f (х)
соответствует некоторый нетривиальный делитель мнО члена f (х).
Остается рассмотреть последнюю возможность: когда и место случай (В) и
коэффициенты aj многочлена f (х) равны для всех 1 < / <; п - 1. Это
означает, что / (х) является д! членом хп + а0 ?Tpd Здесь п не может
делиться на р, -t
а
pd-iy
О / '
как в противном случае мы имели бы f (х) - (хя/р
противоречит неприводимости многочлена f (х) над полем Положим в этом
случае ^
f (х) = Р"7 (Рх + 1), (4
и тогда из того, что Р"1 ф f ^ сразу вытекает, что коэффищ* при xR~! в
многочлене f (х) не принадлежит полю f d. СлеШ
Комментарии
223
тельно, если описанную выше процедуру применить к многочлену f (х), то не
может встретиться случай (В), и мы получим некоторое нетривиальное
разложение многочлена / (х). Но поскольку / (я) =
- Рnf (P_1 (х - 0)* каждому нетривиальному разложению многочлена f (я)
соответствует некоторое нетривиальное разложение
