Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
Ш
Щ
¦
жая тот же процесс для полученных делителей многочлена в конечном счете
получим все корни этого многочлена. Здесь мо было бы заметить, что
описанный алгоритм отыскания кор: многочлена носит не детерминистический,
а вероятностный тер, так как зависит от случайного выбора
соответствующего мента Ь.
4.15. Пример. Найдем-корни многочлена / (х) = х8 + Зх4 - 7jг -f 4х2 -х -
2 ? f17 1x3, содержащиеся в поле Такими корнями являются корни в этом
поле многочл g (х) - НОД (/ (х), х17 - х) и только они. С помощью ал гор"
Евклида находим, что g (х) = х4 + 6х3 - 5х2 -f 7х - 2. отыскания корней
многочлена g (х) воспользуемся алгоритм описанным выше. Возьмем сначала b
= 0; прямое показывает, что х<р~1^2 - хв = 1 (rood g (х))т так что Ь = 0
не приводит к нетривиальному частичному многочлена g(x), Возьмем теперь Ь
- 1; тогда g (х - 1) =
+ 2х3 - Зх - 2 и Xs = -4х3 - 7х2 + Зх - 5 (rood g (х
г.
§ 3. Вычисление корней многочленов
215
и мы приходим к нетривиальному частичному разложению многочлена g {х -
1). Имеем
НОД (g (х - 1), jc8 4 1) - НОД 0х* 4 2ж3 - 3* - 2,
- 4*3 - 7jc* -f 8х - 4) -
- *3 - 7*44,
НОД fe (ж - 1), ж8 - 1) - НОД fe4 4 2*3 - 3* - 2,
- 4** -7*24 8дг - 6) =
- лг2 - 8лг 4- 8, так что из равенства (4.22) получаем разложение
g (х - 1) = fe2 ~7х -h 4) fe2 - 8* -f 8),
которое после замены х на х + I приводит к следующему частичному
разложению для gfe):
g (я) = (я2 - 5я - 2) (я2 - 6я + 1) = gt (я) ga (я).
Чтобы разложить многочлены gx (х) и &.(*), возьмем Ь = 2. Тогда gi (х -
2) - ж2 4 8* - 5 и л? = - 8х 4 2 (mod fe - 2)).
Далее,
НОД fei fe - 2), дв + 1) = НОД fe2 + 8х - 5, -8х 4 3) =
= *4 6;
деление углом дает gx fe - 2) = fe 4 6) fe 4 2), откуда получаем
gx fe) - fe 4 8) fe 4 4).
Обращаясь к g2 fe), получаем, что g2 fe - 2) ~ x2 4 7* = x fe 4 4 7), так
что -2 - корень многочлена g2 fe). Отсюда следует, что
g2 fe) = fe + 2) fe - 8).
В итоге получаем следующее разложение g fe) иа лииейиые множители: g fe)
- fe + 8) fe 4 4) fe 4 2) fe - 8). Поэтому корнями многочлена g fe) (а
значит, и многочлена f fe)) в поле f17 являются элементы -8, -4, -2 и 8.
?
Теперь мы построим алгоритм нахождения корней для случая, когда конечное
поле fg велико, но его характеристика р мала. Как и выше, достаточно
рассмотреть случай, когда
/(я)=П(я-71),
i=l
Г^е У и Yn - различные элементы поля |Г9. Считая, что д - ^ Р4 положим
216
Гл. 4. Разложение многочленов на множители
• ••• • \эе-
ы.
Напомним, что для любого элемента у ? Ftf его абсолщ^ след *S (у) - Trp.
(у) принадлежит простому подполю [р^
определение 2.22). В силу теоремы 2.23(iii)г уравнение S (у) имеет рт~1
решений у ?fq для каждого с ? fp) так что мы д ходим к равенству
лУ - х ~ П (5 (а:) - с). (4;
р
Поскольку многочлен / (х) делит xq - х, мы получаем, что
П (S (х) - с) = 0 (mod / (х)),
откуда
f(x) = П НОД (f(x), S(x) - с). (4
Этот метод приводит к частичному разложению многочлена / и при этом
требуется вычислить всего р наибольших общих телей. Поэтому если р мало,
то указанный метод, безусло пригоден.
Может, однако, случиться, что разложение (4.24) трнвиа (так будет, если S
(х) = с (mod f (х)) для некоторого с ?
В таком случае следует использовать другие вспомогател многочлены,
связанные с S (х). Пусть р - образующий зле поля над Fp, так что {1, р,
р2, ..., pm_1) - базис Fq над Подставляя р/х, 0</< т- 1, вместо х в
(4.23), получ
€
(р/>х?
Р;х - П (5(р/х)
*егр
с).
\Л
Так как (р/)?
р/, то
Xs - х - р~/ П (5 (р/х) - с).
с € Fp
Ь
' щ
Это приводит к следующему обобщению разложения (4.24):
/до
П НОД (/ (х), *S(p/x) -с) для любого /,
€ Fp
О с / < m - 1.
.
• < • г
/й
<
. у-?/ ..
• &
. 4" \ -
т
(4-1
•Г'Э
Покажем теперь, что если п - deg (/) ^ 2, то существует по ней мере одно
значение /, 0 < / < т - I, для которого части! разложение (4.25)
нетривиально. Предположим противное, что все частичные разложения вида
(4.25) тривиальны. Тогда каждого /, 0 < / с т - 1, существует такой
элемент Cj
что
S (р/х) = Cj(mod/(x)).
§ 3. Вычисление корней многочленов
217
В частности, для (различных!) корней уг и у2 многочлена f получаем
S (p/yi) = S (р^уз) = Cj для всех /, 0 < / с тп - 1.
В силу линейности следа это означает, что
Тгг, ((тх - Т2) РО = 0 Длв всех /. О < / < тп - 1,
так что
TrF, ((Ti - VJ ") = 0 Для всех a?Fq.
Применяя вторую часть теоремы 2.24, мы тогда заключаем, что Yj'- у2 ^ 0,
получая противоречие. Таким образом, по крайней мере для одного значения
/, 0 < / с m - 1, частичное разложение
(4.25) нетривиально.
Образующий элемент р Поля Tq над используемый в разложении (4.25), можно
выбрать как корень какого-либо заданного неприводимого многочлена степени
m из кольца Fp [х]. Получив нетривиальное разложение вида (4.25), мы
затем тот же метод применяем к найденным нетривиальным сомножителям
многочлена /, используя другое значение /. Рассуждение, приведенное выше,
показывает также, что, перебирая разные значения / в (4.25), мы в
конечном счете можем найти все корни многочлена {.
