Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 49

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 49)

Теорема. В обозначениях, введенных выше, для всех д имеет место равенство бд (х) = д; (х). Доказательство. Учитывая делимость многочлена гд д на прямой индукцией получаем, что г,(х) = — хег(шаг[с"д д(х)) для всех д) 1. (4 еа Докажем теперь при помощи индукции, что я гд д= П аз и г[;=д, для всех 1>~1. (4Л гз д ПРи д = 1 пеРвое Равенство выполнЯетсЯ, посколькУ ге = г*.

тТ касается второго равенства, то в силу (4.17) д(д (х) = НОД (р~ (х), г, (х) — х) = НОД (г (х), хе — х), ": 4 2. Разно!нелле многочленов над болыннмн яонечнммн полямн 211 и поскольку двучлен хе — х равен произведению всех нормированных линейных многочленов из кольца Кя [х ), то многочлен /1! является произведением всех нормированных линейных многочлепов нз 1[4 [х), которые делят/, так что/1! = 8!. Теперь предположим, что равенства (4.18) выполняются для некоторого ! .

1. Тогда (4.19) так что первое равенство из (4.18) доказано для ! + 1. Кроме того, из (4.17) получаем !+1 !/!„(х) = НОд(Р/ (л), г„, (х) — х) = НОд (р, (х), хя — х). !+! В силу теоремы 3.20 двучлен хе — х является произведением всех нормированных неприводимых многочленов из Г [х1, степени которых делит число ! + 1. Поэтому многочлен /[!, является произведением всех нормированных неприводимых многочленов пз ['„[х), которые делят г! и степени которых делят ! + 1. Из (4.19) тогда следует, что ![„! = и!„. П В изложенном алгоритме самым сложным шагом (с вычислительной точки зрения) является нахождение многочлена г, путем приведения многочлена ге!, по модулю г"! !.

Общая техника сокращения вычислительной работы при этом основана на предварительном нахождении вычетов по модулю Р! ! многочленов г,, 4 ае е г !, г! !, ..., г! ! (где 2 — наибольшая степень двойки, не превосходящая //) последовательным возведением в квадрат и приведением по модулю г! с последующим перемножением того набора полученных вычетов, который дает нужную нам степень г) ! многочлена г!, по модулю г!, Например, чтобы получить вычет степени г,'а, по модулю г! !. нужно перемножить вычеты степеней '-!, г/ !, г, ! и г! ! по модулю г! !. Однако вместо техники повторных возведений в квадрат мы ь'огли бы для нахождения многочлена г; (х) по известному гьл (х) использовать матрицу В из алгоритма Берлекэмпа (см. 5 1). Пусть п = ![еа! (/) н в — ! г !(х) = Е г(''!!хl.

/=е * Определим вектор (ф'1, а)!!, ..., э[~" ") ~ 1['", матричным равенством (з'а/ )!1 !" !!) = ( !е/ !'! г!",'!) 3, (4.20) 14а Гл. 4. Разложение многочленов на множителе где  — матрица порядка п из (4.5). Если ввести многочлен л — ! гч(х) = д з!Ох', (4.21) г=е то получим, что г,, (х)е : =з, (х) (пзое) 1 (х)), откуда г;, (х)е =: := з; (х) (шог) Е,, (х)), так что г;(х) =: з;(х)(шог)В; г(х)). Поэтому если известна матрица В, то на каждом шаге 1 мы, зная многочлен гг г (х), можем найти многочлен г, (х) приведением по, модулю г";, (х) многочленов з, (х), получаемых из (4.20) и (4.21).'! 4.14. Пример.

Рассмотрим тот же многочлен ) (х) =- х' — ' — Зх'+ 5х' — 9хв — бх'+ бх + 7 ~ Гез (х), что и в примере,' 4,7. Тогда матрица В имеет вид 1 0 0 0 5 0 — ! 8 — 10 10 10 0 0 7 9 — 8 11 0 — 4 7 — 3 0 — 1О 9 О 0 — 3 — 10 1 — 9 10 — 11 7 2 2 — 9 1(х) = (х — 4) (х' — х + 7) (ха + 2х'+ 4х — 6), которое в данном случае уже оказывается каноническим разложением многочлена ) (х) в кольце Кзв (х).

(:) Начнем алгоритм с г, (х) = х и Ге (х) =- ! (х), Из (4.20) и (4,21) получаем многочлен л, (х) = — 10х' — Зх' + 8х' — хз + 5, и, при-, водя его по модулю ге (х), находим г, (х) = — з, (х). Согласно тео-, реме 4.13, имеем дг (х) =- г(з (х) = — НОД (В, (х), г„(х) — х) = х — ' — 4. Кроме того, Е, (х) = Ре (х)Яг(, (х) = х'+ х' + 9х' + 4х' + ' + 11х+ 4.

На втором шаге мы вновь применяем (4.20) и (4.2!) для нахождения многочлена з, (х) = 5х' — 8х'+ 9ха — 10х' — 11, и приведением его по модулю г", (х) получаем г, (х) = 1Ох'+ 10х'— — 7х' — 9х — 8. Согласно теореме 4.13, йв (х) = г(з (х) = . = НОД (г, (х), г, (х) — х) = х' — х + 7. Кроме того, Ез (х) = === Гг (х)Яз (х) = х' -!- 2х'+ 4х — 6. Но, согласно первой части (4.!8), все неприводимые делители многочлена Ге (х) имеют степени не менее 3, поэтому многочлен Ве (х) сам должен быть неприводимым в кольце Квз (х), так что уз (х) =- Ев (х).

Таким образом, мы получаем частичное разложение $ 3, Вычисление корней миогочлеиои 2!3 $3. Вычисление корней миогочленов В предыдущих параграфах мы видели, что проблему канонического разложения некоторого многочлена над конечным полем часто можно свести к задаче нахождения корней в этом поле некоторого вспомогательного многочлена. Но вычисление корней многочлена, безусловно, представляет и самостоятельный интерес. Вообще говоря, мы ставим следующую задачу.

Пусть задан многочлен ) ~ [!„[х); требуется найти его корни в некотором расширении К» поля Г„. Однако достаточно рассмотреть ситуацию, когда нужно найти корни многочлена ) ~ [['» [х[ положительной степени, лежащие в самом Г», так как многочлен над подполем всегда можно рассматривать как многочлен над всем полем, Ясно, что каждый алгоритм разложения многочлена [ в кольце г'» [х), в частности, является и алгоритмом нахождения его корней в поле К», так как эти корни определяются линейными сомножителями канонического разложения ) в кольце К [х1. Поэтому алгоритмы, рассмотренные в предыдущих параграфах этой главы, можно использовать также и для нахождения корней. Однако эти алгоритмы чаще всего являются не самым эффективным способом вычисления корней многочлена, когда ставится именно такая задача.

Поэтому мы рассмотрим методы, более приспособленные для этой цели. В качестве исходного шага полезно выделить ту часть много- члена г, которая содержит все его корни в поле г». Зто достигается вычислением НОД (~ (х), х» — х). Ввиду того что двучлен х» — х является произведением всех нормированных линейных много- членов кольца г» [х1, указанный наибольший общий делитель равен произведению всех тех нормированных линейных многочленов над [['», которые делят г; поэтому его корнями являются те и только те корни многочлена ~, которые принадлежат полю г». Учитывая это, можно без ограничения общности предполагать, что все корни многочлена, для которого мы намерены найти корни в поле г», принадлежат полю [['» и притом различны, т.

е. что 1' является произведением различных линейных нормированных миогочленов из [[' [х 1. Один полезныи метод нахождения корней многочленов мы уже рассмотрели в 3 4 гл. 3; он был основан на определении аффинного кратного для данного многочлена.

Этот метод мы проиллюстрировали примером 3.55. Переходя к другим методам, рассмотрим сначала случай простого поля К . Как уже было отмечено, достаточно рассмотреть лишь многочлены вида ~(х) = П (х — с!). е=! 214 Гл. 4. Разложение многочленов на множители где с,, ..., с„— различные элементы поля гл, Если чи мало, то найти корни многочлена Г можно просто методом п ошибок, т. е. простым вычислением всех значений Г (О), 7 (1 ' ",7 (и — 1) Если же число р велико, то можно применить следующий ем. Пусть Ь ~ К'н, где р нечетно. Рассмотрим равенство 1(х — Ь) = П (х — (Ь+с;)).

г =! Заметим, что многочлен Г" (х — Ь) делит двучлен хн— = х (х<л — '>~'" + !) (х<л — >>!' — !). Если при этом х является телем многочлена г (х — Ь), то г" ( — Ь) =- О, и нами найден из корней многочлена Г', Если же х не является делителем Г (х то ~ (х — Ь) = НОД (~ (х — Ь), х<л — '>!е + 1) НОД (( (х — Ь),'; х<а — <>г' — 1). (4 Равенство (4.22) мы теперь используем следующим образом.

ведем степень х<а — '>М по модулю Г (х — Ь) (например, прим технику последовательною возведения в квадрат, рассмотрен' вслед за теоремой 4.13). Если х<л->><' чез ~! (гпод Г (х — Ь))!' равенство (4.22) даст нетривиальное частичное разложение м члена 7" (х — Ь). Заменяя х на х + Ь, мы получим нетривиа частичное разложение многочлена Г (х). В довольно редком чае, когда х<л — '»а =— + 1 (<по<! г' (х — Ь)), можно использо другое значение Ь. Таким образом, изменяя по мере необходи выбор элемента Ь, мы можем найти либо некоторый корень м члена 7', либо его нетривиальное частичное разложение. Пр " жая тот же процесс для полученных делителей многочлена Г,'!' в конечном счете получим все корни этого многочлена. Здесь мо было бы заметить, что описанный алгоритм отыскания ко многочлена носит не детерминистический, а вероятностный ха тер, так как зависит от случайного выбора соответствующего мента Ь.

4.15. Пример. Найдем корни многочлена 7 (х) = х' — '7Х<н: + Зх' — 7хз + 4х' — х — 2 Е !Г<т [х!, содержащиеся в поле 1!!" Такими корнями являются корни в этом поле многочл й'(х) = НОД (г (х), х" — х) и только они. С помощью алгор Евклида находим, что д (х) = х' + бха — 5х' + 7х — 2. отыскания корней многочлена д (х) воспользуемся алгоритм, описанным выше. Возьмем сначала Ь = 0; прямое вычисле показывает, что х<л — '»е =- х' = ! (п>о<1 д (х)), так что знач Ь = 0 не приводит к нетривиальному частичному разложе многочлена д (х), Возьмем теперь Ь = 1; тогда д (х — 1) = х',", + 2х' — Зх — 2 и ха з— е — 4хз — 7ха + 8х — 5 (гпо<1 и (х — а 4 3. Вычисление корней ыногочленов и мы приходим к нетривиальному частичному разложению мно- гочлена д (х — 1).

Характеристики

Список файлов книги