Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 51
Текст из файла (страница 51)
Е=-! Построим теперь многочлен м — ! г (х) = П )« (х) Это многочлен над полем Гр, так как ж — ! л л т-! л г (х) =- П П (х — уи ) = П П (х — уР ) = П г ! (х) глг, «=о о=! с=! «=о !=-! где г! (х) — минимальный многочлен элемента у, над полем 1Г а о(! — его степень (ср.
с материалом, предшествующим тео 2.23). Поэтому многочлены и! (х) являются неприводимымн множителями многочлена г" (х) в кольце Гр (х), но некоторые них, вообще говоря, могут совпадать между собой. Значит, ка!( ионическое разложение многочлена и" (х) в кольце Гр (х) им вид г (х) = 6,(х)... 6„(х), (4М где 6! (х), ! ~ 1 ~ г, — степени различных неприводимых мне:, ' членов г! (х), Это каноническое разложение может быть получ с помощью одного из алгоритмов, изложенных в 5 2 этой глав, 5 3. Вычисление корней многочлеиов 22! Поскольку многочлен / (х) = /е (х) делит Р (х), то из (4.31) сле- дует, что /(х) = П НОД(/(х), а,(х)).
(4.32) Формула (4.32), как правило, дает нетривиальное частичное разложение многочлена /(х). Тривиальным оно является в том и только том случае, когда НОД (/ (х), бг (х)) = / (х) для какого- нибудь /, 1 < ! < г, что эквивалентно условию г = 1 '), и тогда / (х) делит Рг(х). Сравнение степеней показываетв), что п < с(, = пт. Кроме того, корни многочлена /(х) в этом случае все сопряжены относительно поля Рр. Таким образом, мы можем записать (изменив, если нужно, нумерацию корней многочлена /(х)) у, = у', ', 1(!.(п, где О = Ь, -Ье.(...
(Ь„(т. Положим Ь„„= т и с(= — ппп (Ь„г — Ь,). Ясно, что с( < т/п. 1<г<п Могут встретиться следующие две возможности: (А) Ь;„— Ь, > с( для некоторого /, 1 < г < и; (В) Ь;„— Ь; = г( для всех г, 1 а г < а. В случае (А) заметим, что множеством корней многочлена / (х) является (Тн" ун' "' ув'"~ а множеством корней многочлена /„(х) является (,' ь;ьа ь,+л ь„+а~ у," ТГ' . у'," Из условия (А) следует, что эти два множества корней не совпа- дают.
Но, с другой стороны, поскольку Ьг„— Ь; = с( для неко- торого ~', 1.( г ( а, эти два множества корней содержат общий элемент, Таким образом, многочлен НОД (/(х), /л (х)) отличен как от / (х), так и от 1. Следовательно, НОД (/ (х), /а (х)) является нетривиальным делителем многочлена / (х). Нетрудно видеть так- же, что в этом случае д ( и/и. В случае (В) сравнение множеств корней многочленов / (х) и /а (х) показывает, что / (х) = /,, (х), так что НОД (/(х), /а (х)) = 1 для всех й = 1, ..., г( — !. Кроме того, д = гп/л, так что число и делит т, и, значит, Ь; = с((г' — 1) для ! = 1, ..., и.
гл гд — 1! о д. „,д„„, 1 ьг ! Так как если сдг (х) = Р; (х) г, то Рг является минимальным миогочленом каждого карня т/ многочлеиа /. — Прим. пери. ') Так как гг содержит все ТП 1 < / < и. Если бы было д/ < пг, то все У/ иРннаклежалн бы Г а, что пйотнвоРечнт выбоРУ д = Р~. — ПРим. пеРед. Р д Гл. 4. Разложение миогочленон на множители т. е. элементами у~ являются элементы, сопряженные с у, отн тельно поля Г ю и только они.
Следовательно, /(х) явля минимальным многочленом элемента у, над К н и, значит, И' и приводим над Г л. р и Поэтому в соответствии со случаями (А) и (В) мы получ следующие две возможности: (А) Многочлен НОД (/ (х), /„(х)) для некоторого К 1 < й' < т/и, является нетривиальным делителем многочлена / ('' (В) НОД(/(х), /„(х)) = 1 для всех я =- 1, ..., д — 1, г( = т/пЕ!Ч, и /(х) = /н (х) — минимальный многочлен э " мента у, над полем К л. Следовательно, в случае (А) наша цель отыскания петри ального делителя многочлена / (х) достигнута. В случае же (В) еще требуется дополнительное исследован" Пусть р снова обозначает образующий элемент поля ге над ф". Тогда ге,()3) = г = Р, так что элемент р имеет степень т/Н =и; над полем Гл,. В частности, это означает, что ффУ л для всех: ! < / < и — 1.
Пусть теперь коэффициенты а, многочлена / таковы, что а;, чь О для некоторого /ео ! ~(/, < и — !. Расс трим многочлен / (х) = р "/ (рх), (4. который является нормированным многочленом степени и над $' Так как р" ' ф К ~, а аб ~ Г ~, то, значит, коэффициент хд в многочлене / (х) не принадлежит полю гл,. Поэтому /: не является многочленом над полем К л, и, следовательно, указанную выше процедуру применить к многочлену / (х), случай (В) не может встретиться, и мы получим некоторый тривиальный делитель многочлена / (х).
А поскольку / (х) = р"/ (р х), то каждому нетривиальному делителю многочл / (х) соответствует некоторый нетривиальный делитель мно члена / (х). Остается рассмотреть последнюю возможность: когда н место случай (В) и коэффициенты аз многочлена / (х) равны нуМ, для всех /, 1 < / < и — 1. Это означает, что / (х) является членом х" + а, ~Кл,(х). Здесь и не может делиться на р, 'т как в противном случае мы имели бы / (х) = (х"~и+алел )", противоречит неприводимости многочлена / (х) над полем ~Г, Положим в этом случае / (х) = (! / (Рх + 1), (4. и тогда из того, что р ' ф г д, сразу вытекает, что коэффнцив,, при х"-' в многочлене / (х) не принадлежит полю гл,.
Сл Комментария тельио, если описанную выше процедуру применить к многочлену [ (х), то не может встретиться случай (В), и мы получим некоторое нетривиальное разложение многочлена г (х). Но поскольку )' (х) = [1"г (р ' (х — 1)), каждому нетривиальному разложению многочлена [ (х) соответствует некоторое нетривиальное разложение миогочлена ( (х). Итак, применяя этот алгоритм отыскания корней многочлена )' (х), мы должны поступать следующим образом. Сначала построим многочлены гд (х) по формуле (4.29) и многочлен г" (х) ~ [х) по формуле (4.30).
Затем, применяя алгоритм разложения из 3 2, находим каноническое разложение (4.31) многочлена Р: (х) в кольце [[р [х); это приводит к частичному разложению (4 32) миогочлена )'(х). Если это разложение оказывается тривиальным, мы находим многочлены НОД Д (х), ~„(х)) для всех я, 1 .:. я < гп!и. Если и это не приводит к нетривиальному разложению многочлена ) (х), мы заменяем многочлен Г (х) многочленом )" (х) из формул (4.34) или (4.33) в соответствии с тем, является ! (х) двучленом или нет.
Как показано выше, применение того же алгоритма к 1 (х) уже обязательно приводит к нетривиальному разложению многочлена г (х), а следовательно, и многочлена Г (х). Как только нетривиальные делители многочлена 1(х) найдены, процедура повторяется с заменой многочлена Г (х) полученными его нетривиальными делителями, и так продолжается до полного разложения многочлена ~ (х) на линейные сомножители, которые, согласно теореме 1.64„и определяют корни этого многочлена. Комментарии $1. Алгоритм разложения, основанный на матрице В (алгоритм Берлекэмпа), был впервые изложен в статье Вег1екагпр [3) и воспроизведен в книге Вег[ейагпр [4, сп.
6[. Возможность использования матрицы В из этого алгоритма для определения числа нормированных неприводимых сомножителей многочлена 1 была замечена еще раньше. В статье Ре1г [1 [ показано, что если зсе неприводимые сомножители многочлена ! различны (т, е. в разложении (4.1) е, = ... = е„= 1), то характеристический многочлен де! (х1 — В) матрицы В равен произведению двучленов (х"' — 1) „. (х "— 1), где и, =- дея (д,), 1 = 1, ..., я.
Общий случай был исследован Шварцом, показавшим в статье Яс[пчагг [1 ), что де! (х! — В) =х (х ' — 1) „(х" !), где т = ~' л,(е, — 1); Ггн см также Ьспчгагх [11 [. Результат, состоящий в том, что ранг матрицы  — у равен л — Ф, установлен Батлером (Вц[[ег [! [): другое его доказательство дано Шварцом (Бс[пчагз [111). В статье Ж!!!е[1 [5[ число й интерпретируется как размерность 224 Гл. 4. Разложение миогочленон на множители векторного пространства линейных рекуррентных последова , в ностей (см. гл, 8). Алгоритм Берлекэмпа излагается в следу работах: СЛ~!г[з 11, раг! 11, сЬ. 121, СоИ!пз [3 1, Кпц[Ь [3, сЬ, 1.Ы[, РИх [1, сЬ.
71, М!япо!!е [3! и 2!шгпег 12, сЛ. 2!. Алгоритмы, основанные на многочленах Т; (см. теорему и [7, (см. теорему 4.5), построены Макэлайсом (МсЕ[!есе В его же работе МсЕ1е!се [31 приводятся таблицы разложен' двучленов х" — 1, полученные применением этих алгори Изложение этих и других алгоритмов разложения можно и также в работах СоИ!пз 131, Кпц!Ь [3, сЛ. 4), 1.Ы[, %!езепЬ [1, сЬ. 2), М!япо!1е 13) и Лпптег [2, сЛ. 2 !. Матрицу В можно также использовать для определения ч пн различных нормированных неприводимых делителей степем" (1 ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
