Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 50
Текст из файла (страница 50)
Имеем НОД(й(х — !), х + 1) = НОД("+2* — З вЂ” 2, — 4хв — 7хе + 8х — 4) = = хе — 7х+ 4, НОД (я (х — 1), х' — 1) = НОД (х' + 2х' — Зх — 2, — 4хе — 7хе+ 8х — б) = = х' — 8х+ 8, так что из равенства (4.22) получаем разложение й (х — !) = (хе — 7х + 4) (х' — Зх + 8), которое после замены х на х + 1 приводит к следующему частич- ному разложению для д (х): д (х) = (х' — бх — 2) (х' — бх + 1) = я, (х) ие (х).
Чтобы разложить многочлены «г (х) и яе (х), возьмем Ь = 2. Тогда д, (х — 2) = хв + 8х — б и х' = — 8х + 2 (гпог( дг (х — 2)). 7!злее, НОД (д, (х — 2), х' + 1) = НОД (х' + Зх — 5, — 8х + 3) = =х+ б; деление углом дает л, (х — 2) = (х+ б) (х+ 2), откуда полу- чаем д, (х) = (х + 8) (х + 4). Обращаясь к де (х), получаем, что де (х — 2) = х' + 7х = х (х + 7), так что — 2 — корень многочлена ие (х), Отсюда следует, что яе (х) = (х + 2) (х — 8). В итоге получаем следующее разложение я (х) на линейные мно- жители: д (х) = (х+ 8) (х + 4) (х + 2) (х — 8).
Поэтому корня- ыи многочлена и (х) (а значит, и многочлена 7'(х)) в поле Гм Яв- ляются элементы — 8, — 4, — 2 и 8. П Теперь мы построим алгоритм нахождения корней для случая, ~огда конечное поле гч велико, но его характеристика р мала. 1(ак и выше, достаточйо рассмотреть случай, когда е 7(х) = П (х — У,), г-1 "де уп ", у„ — различные элементы поля гч. Считая, что д = ' - Р, положим щ — 1 3(х)= Я хр. г-о 2!6 Гл. 4.
Разложение многочленов иа множители Напомним, что для любого элемента у ~ К» его абсол след 5 (у) = Тга (у) принадлежит простому подполю » Р определение 2.22), В силу теоремы 2,23(ш)„уравнение 5 (Т) ' имеет р — ' решений у ЕК» для каждого с Е Кр, так что мы ходим к равенству х» — х =-. П (5 (х) — с). (4 »~ар Поскольку многочлен г (х) делит х» — х, мы получаем, что П (5 (х) — с) с— а О (шод ~ (х)), се»р откуда у(х) =- П Нодд(х), 5(х) —.). се!Гр Этот метод приводит к частичному разложению многочлена Т' и при этом требуется вычислить всего р наибольших общих д телей. Поэтому если р мало, то указанный метод, безусло пригоден.
Может, однако, случиться, что разложение (4.24) тризна (так будет, если 5 (х) = с (шод Г(х)) для некоторого с ~ В таком случае следует использовать другие вспомогатель, многочлены, связанные с 5 (х). Пусть )) — образующий эле поля К над Гр, так что !1, р, )Р, ..., р — ') — базис К» над' Подставляя р!х, О ~ / и: т — 1, вместо х в (4.23), получ $!)»х» — Ргх = П (5 фгх) — с). ° й!Гр Так как (р!)» = ()!, то х» — х = ~ — ! П (5 (~!х) — с). сеГр Это приводит к следующему обобщению разложения (4.24): )(х) = П НОД(г'(х), 5(р»х) — с) для любого /, се!Гр О~у~т — !.
(4, Покажем теперь, что если и =- г(ед (Г) ) 2, то существует по кр ней мере одно значение 1', О ~ 1' ~ т — 1, для которого части разложение (4.25) нетривиально. Предположим противное, тй что все частичные разложения вида (4.25) тривиальны. Тогда, каждого 1', О ~ / ( т — 1, существует такой элемент с~ ~ что 5 (р!х) г— а с,(шод((х)). $3. Вычисление корней нногочленон 217 В частности, для (различных)) корней у, и у, многочлена 7' получаем 5(В'И = 5(В'уз) =с, для всех 1, О ~!.~лг 1. В силу линейности следа зто означает, что Тгу' ((Уг — У,) В') =- О для всех у, О < ) < т — 1, так что Тг1гвЯУг — У,)а) =О дла всех а~К Применяя вторую часть теоремы 2.24, мы тогда заключаем, что т, - — у, = О, получая противоречие.
Таким образом, по крайней мере для одного значения 1, О ~ 1 ~ т — 1, частичное разложение (4 25) нетривиально. Образующий злемент В поля з в над Гр, используемый в раз- ложении (4.25), можно выбрать как корень какою-либо заданного иепризодимого многочлена степени т из кольца Кр ]х]. Получив нетривиальное разложение вида (4.25), мы затем тот же метод применяем к найденным нетривиальным сомножителям много- члена 7, используя другое значение 1.
Рассуждение, приведенное выше, показывает также, что, перебирая разные значения )' в (4.25), мы в конечном счете можем найти все корни многочлена 7. Пример 4.16. Рассмотрим поле Гвь = Кз (]1), где  — неко- торый корень непрнводимого многочлена хв + х+ 1 из Гз (х], и пусть 1'(х) =- х'+ (В'+ В'+ В'+ В') х'+ (В'+ В'+ В'+ В+ + 1) х'+ (Вв + ])з + В) х + (Вз + В) Е Гвв (х]. Используя сравнение хв — (Вь+ В+ 1)хз+ (Вв+ Вз+ Вз)хз+ (Вь+ Вз+ Вз+ 1) х ] (Вь -]- Вв+ Вз+ 1) (пьоб 7 (х)), получим последовательным возведением в квадрат следующие сравнения по модулю 1 (х): хн х, хг = хэ, хг — (Вь ( Вг 1 Вэ ( Вэ)хэ 1 (Вь, Вв 1 Вэ+В+1)эе+(В~+В~+В)х+(В +В)' (Вг+Вэ+Вг) хе+ (Вь+В+Пх'+ (Вг+В+1) х+(В'+В') (Вь 1 Вэ 1 В)„э+ (Вэ ( В) хг+ В'х+(В'+В'+В'+В+1) (Вь 1 Вэ 1 1) „,э ( (Вь+Вг.( Вэ-;.В'-)-В+1)х'+ (В'+В') х+(В~+В') х"— Т.
аким образом, многочлен 7 (х) делит двучлен х'в — х и, следова- тельно, имеет четыре различных корня в поле Гвв. Рассмотрим в!в Гл. 4. Разложеиие миогочлеиоз иа миожители теперь многочлен 5 (х) = х + хз + х' + х' + х" + х". Из пр веденных выше сравнений получаем, что 5() фь+ Рз ! ~з+ Р+ 1) ел ()ьхз+(~з+ Рх+ < + ф' + (Р + 1) (той ( (х)), так что НОД (Г (х), 5 (х)) = НОД Д (х), ф" + )Р+ (Р+ 13 + 1) хз + + рьхз + ф' + ()з) х + ф' + ))з + 1)) = =- х' + ф' + 1' + 0') х' + ф' + ()' + 1) х + ф' + (Р) = а и НОД Ц (х), 5 (х) — 1) =- НОД Ц (х), ф' + ~з -1- (Р + ~ + 1) „з ! ()ьхз ! фз ! ииз)х ~ фз ! ииз) =х+ рь.
Поэтому из (4.24) получаем Г (х) = а (х) (х + рь). (4. ' Чтобы найти корни многочлена д (х), мы теперь применим ра жение (4.25) с 1 = 1. Поскольку 5 фх) ))х ь гизхз гиьхь 1 гивхз ! ()гильз + газзхзз = ()х + изхз + ньхь + фз -1- из) хз -1- -'; ф' + н + 1) хьа -1- ф' -1- 1) х'з, то из полученных выше сравнений вытекает, что 5ф,) фз ! 1)хз ! фз ! ои 1 1) з+(ииь ! Роз+ ииз + (Р + р + !) х + ф' + рз + р) (пюг( Г (х)). Так как многочлен д (х) делит Г (х), то это сравнение выполннетс также и по модулю л (х), поэтому 5фх) — фз+!) + фз+ 1+ 1)хз+ фь+ 1ь+(!3+ + 1' + 1 + 1) х + ( 0' + ()' + ()) Ги — фь + ))з) Хз 1 )ьзХ ) фь ! рз + р) (ШОГ) Ьг (Х)) Таким образом, НОД(д (х), 5 фх)) = НОД (д (х), ф'+ ~') х'+ ~'х+ + ф'+ р'+ р)) = з 1 фз 1)х ! фь ! ()з + оиз 1 ь)) ь (х НОД (д (х), 5 фх) — 1) =- НОД (и(х), (~Р -4- ~з) хз + ~ах+ + ф'+ 1'+ 0 + 1)) = = х+ фь+ ~а+ 1).
4 3. Вычисление корней ыногочлеиов гв Поэтому для / = 1 из (4.25) получаем, что д (х) = й (х) (х + ф' + рз + 1)), (4.27) цтобы найти корни многочлена Л (х), снова применим разложение (4.25), но возьмем 1 = 2. Поскольку с фвх) Рзх + ()вхз 1 инв в + изв в 1 ~зз вв 1 ()вв зз иЯгх 1 иивхз 1 фз 1 низ) хв 1 (оив + Р + 1) в+ фз + 1) хзв 1 ни зз то такой же подсчет, как и для 5 фх), дает 5 ф'х) г— и фв -1- из+ 1) х+ фв+ аз+ яз) (п1об 8 (х)). Поэтому НОД (Ь (х), 8 ф'х)) = НОД (й (х), ф' + рз + 1) х + 13в + +р +Р)= = х + (р + 1), НОД (л (х), Я ф'х) — !) = НОД (й (х), ф' + рг + 1) х + иЯв 1 иЯз 1 Рг 1 1) + ф'+ ~), так что нз (4.25) для 1 = 2 мы получаем й(х) =(х+6+ 1)(х+6з+6). (4.28) Объединяя (4.26), (4.27) и (4.28), получаем следующее разложение миогочлена )': ) ( 1 1 1)( 1 оз+())(х 1 нив 1 сиз+1)(х+13в), так что коРнЯми многочлена 7 (х) в поле Квв ЯвлЯютсЯ элементы 1+1 63+6,8в+6з+1ибв (:) И наконец, мы рассмотрим проблему отыскания корней много- члена для случая большого конечного поля Кч с большой характеристикой р.
Как уже говорилось раньше, достаточно выяснить, как находить корни многочленов вида л )(х) = П (х — ув) сан с различными элементами у„..., у„Е Гч. Для выяснения вопроса, будет ли данный многочлен 7 (х) иметь такой вид, достаточно лишь проверить выполнение сравнения хв = х (аюпов( (~ (х)) (ср. с первой частью примера 4.16). Мы можем предположить, что д— наименьшая степень характеристики р, для которой выполняется Гл. 4. Разложение многочленон иа множители 220 это сравнение.
Многочлен )'(х) зададим стандартным предста нием ~(х) = ~~ а!х', г=о где а; Е Го длЯ О ~ 1 ( и и а„= 1. Нашей первой целью будет отыскание какого-нибудь истр анального делителя многочлена ) (х). Чтобы исключить тривиал" ный случай, предположим, что и ) 2. Считая, что д = р , ра" смотрим многочлеиы л («(х) = 2з а) х, А = О, 1,..., т — - 1, (4, !'=.о так что Го (х) == Г (х) и Г«(х) — ноРмиРованный многочлен наД для каждого и, О ~ й ~ т — 1. Нетрудно видеть, что для в '' 1и:! ки, и К О~й<т — 1, о («(угР ) = Е а,' у!!" = ~ ~~ а!.у,'.~ = О, г=-о г=о так что И « )«(х) = П(х — ур ), й = О, 1,..., т — 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
