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

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

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

3. Миогочлеиы иад конечными полями 3.94. Доказать, что если г) Е 9) — нечетное число, то круговой много ' ()а ц Гз [х) делит некоторый трехчлен иэ [Гя [х) тогда и только тогда, кот ' кратно трем. 3.93. Пусть )(х) = х" + ах + Ь Е 1Ге [х), и ~ й >1, и пусть ч гл ц 3) кратно огг) (Гь Доказать, что /(х) делит трехчлеи д(х) = х"', +Ь 'х" +аЬ 3.96. Доказать, что трехчлен хз" + х" + ! иеприводнм над полем Кз н только тогда, когда и = За для некоторого целого неотрицательного чи 3.97. Доказать, что трехчлен хеа + «" + 1 иеприводим над полем Ез.

н только тогда, когда л = Зяб~ для некоторых целых неотрицательных чн и гн. Глава 4 Разложение многочленов на множители Любой непостоянный многочлен над заданным полем можно разложить в произведение неприводимых многочленов. Если рассматриваемое поле конечно, то для фактического вычисления иеприводимых сомножителей данного многочлена положительной степени над этим полем сушествуют весьма эффективные алгоритмы. Наличие таких алгоритмов для многочленов над конечными полями особенно важно для теории кодирования и для изучения линейных рекуррентных соотношений в конечных полях. Но и вие области конечных полей в алгебре и теории чисел имеется много вычислительных задач, которые так или иначе связаны с разложением многочлеиов над конечными полями.

В этой связи можно упомянуть, например, разложение на множители многочленов над кольцом целых чисел, отыскание разложений простых рациональных чисел в полях алгебраических чисел, вычисление группы Галуа некоторого уравнения над полем рациональных чисел и построение расширений полей. Здесь будет изложено несколько алгоритмов разложения много- членов над конечными полями, Выбор конкретного алгоритма обычно зависит от того, «малым» или «большим» является данное конечное поле. В $ ! мы опишем те алгоритмы, которые более удобны для «малых» полей, а в й 2 — те, которые лучше работают для <больших» конечных полей.

Некоторые из этих алгоритмов сводят проблему разложения многочленов к задаче отыскания корней некоторых других многочленов. Поэтому в $ 3 вопрос об отыскании корней многочленов рассматривается с вычислительной точки зрения. В 1. Разложение многочленов иад малыми конечными полями Для любого многочлена !' Е К«!х! положительной степени сушествует каноническое разложение в кольце Г, !х! (теоРема Е59). При построении алгоритма такого разложения, очевидно, достаточно ограничиться рассмотрением лишь нормирован- Гл. 4. Разложение многочленов иа множители 188 нык многочленов.

Таким образом, нашей целью является пр ставление ноРмиРованного многочлена 1 Е Еч (х) положит ной степени в виде произведения гДе Гм ..., ~а — Различные ноРмиРованные непРиводимые дед' тели многочлена 1 в кольце Е (х), а гп ..., ел — натураль числа. Прежде всего мы упростим свою задачу, показав, что указац, ную проблему можно свести к проблеме разложения многочлеп без кратных неприводимых сомножителей, т. е.

такого мно ' члена (, для которого в каноническом разложении (4.1) все пока' затели е„..., га равны единице (это равносильно отсутствию у мн"' гочлена 1 кратных корней). Для этого мы сначала найдем, при няя алгоритм Евклида, многочлен д (х) =- НОД () (х), Г' (х)) — наибольший общий делитель многочлена 1 и его производной ~'.~а Если й (х) = 1, то в силу теоремы 1.68 многочлен Г (х) не и кратных сомножителей '). Рассмотрим случай, когда И (х) й) = ~ (х). Тогда, очевидно, должно быть 1' (х) =- О, а это знач что ) (х) = д(х)а для некоторого многочлена йг(х) ~ Еа Ь где р — характеристика поля Еч.

Указанную процедуру реду цин можно, если это необходимо, повторить применительно к мв, гочленуд(х) и т. д., пока не получим представление ) (х) = Ь (х где й' (х) ~ О, ь Если же многочлен й (х) отличен от 1 и ото (х), то он явля нетривиальным делителем многочлена ) (х), и в этом случае мне член Г" (х)lй (х) не имеет кратных неприводимык сомножител Мы придем к разложению 1" (х), разложив по отдельности мног, члены меньшей степени й (х) и ~ (х)Я(х). В случае если много й (х) все еще имеет кратные множители. мы для него повторя, указанный процесс редукции. Применив этот процесс нужное число раз, мы сведем исходи проблему к задаче разложения некоторого числа многочлено' не имеющих кратных неприводимых сомножителей. Каноническ, разложения этих многочленов сразу же приведут к каноническо разложению исходного многочлена.

Эти соображения позволя нам сосредоточить свое внимание на многочленак, не имеющ кратных неприводимых сомножителей. Следующая теорема я ляется основной. ') Речь идет о каноническом разложении. — Прим. нерва. 4 !. Разяожеяие мяогоялеяов яад малыми кояячиымя полями !89 4.1. Теорема. Если ) Е Гч !х) — нормированный многочлен полохсительной степени и многочлен Ь Е !Гя !х! удовлетворяет условию Ья = Ь (шоб ~), то 1(х) = П НОД(г(х), Ь(х) — с).

(4.2) 'ЕГя доказательство. Каждый наибольший общий делитель из правой части равенства (4.2) делит многочлен 7' (х). Поскольку миогочлены Ь (х) — с, с ~ 1я, попарно взаимно просты, то взаимно простыми являются й их наибольшие общие делители с 1(х), т. е. сомножителя пРавой части (4.2), и, следовательно, правая часть равенства (4.2) делит миогочлен ) (х). С другой стороны, многочлен 1(х) делит разность Ь (х)Я вЂ” Ь (х) = П (Ь (х) — с), 'Е!Гя и, значит, 1(х) делит правую часть равенства (4.2). Итак, обе части (4.2) являются нормированными многочленами, каждый из которых делит другой, и, значит, они должны совпадать.

( ! Вообще говоря, формула (4.2) не дает полного разложения миогочлена 1, поскольку многочлен НОД (~ (х), Ь (х) — с) может оказаться приводимым в кольце Гя !х !. Если же Ь (х) = == с (шоб ! (х)) для некоторого с ~ !Гя, теорема 4.1 вообще приводит к тривиальному разложению ) (х) и потому бесполезна. Если многочлен Ь (х) таков, что теорема 4.1 приводит к нетривиальному разложению многочлена ) (х), он называется )-разлагающим многонленом. Любой многочлен Ь Е !Гя (х), обладающий свойствами Ья = Ь (шоо )) и О < бед (Ь) < бед (7), очевидно, является 1-разлагающим. Чтобы на основе теоремы 4.! получить алгоритмы разложения, мы должны найти способы построения 1-разлагающих многочленов. Но уже на этом этапе ясно, что, поскольку разложение, основанное на формуле (4.2), связано с вычислением а наибольших общих делителей, то прямое применение этой формулы возможно лишь для малых конечных по'!ей Гя (т. е.

для небольших значений 4). Первый способ построения )-разлагающих многочленов использует китайскую теорему об остатках для многочленов (см. упр. 1.37). Допустим, что многочлен ) не имеет кратных сомножителей, так "то 1 = 11 ... !я — произведение различных нормированных не- приводимых многочленов над полем !Гя. Тогда длЯ любого Ь- набора (с,, ..., с ) элементов поля !Гч, согласно китайской теоРеме об остатках, существует едийственный многочлен Ь Е с Гя !х ), такой, что Ь (х) : =с! (шоб 1! (х)), 1 «( 1 «( Ь, и бей (Ь) < бей ()).

Этот многочлен удовлетворяет условию Ь(х)' гэ св! =— с! = — Ь(х)(пккн)!(х)), 1=1,, Ь, Гл. 4. Разложение нногочленов на множители 190 и потому Ис г— а И(шоб Г), бед(И) < реп Ц). (4. Ф С другой стороны, если многочлен И является решением срази ния (4.3), то из равенства И(х)о -- И(х) = П (И(х) — с) сер в силу попарной взаимной простоты сомножителей правой ча следует, что каждый неприводимый делитель многочлена 1 доны жен делить один и только один из многочленов И (х) — с. Такнзр образом, каждое решение И (х), беи (И) < бей (1), сравнения (4.3 удовлетворяет системе сравнений И (х) гз с; (шой 1! (х)), = 1, ..., И, для некоторого И-набора (с,, „с„) элементов поля !г" -„- Следовательно, сравнение (4.3) имеет ровно дь решений. Чтобы найти эти решения, сведем сравнение (4.3) к систе линейных уравнений. Полагая с(ея (1) = и и вычисляя хго по мог' дулю 1(х), построим ахи-матрицу В =- (Ьы), О ~ 1, 1 ~( и — 1!)Р А именно л — ! хго г— э ~ Ьгэхь(гпоб)'(и)), ! = О, 1, ..., и — !.

(4.' 1=о Тогда многочлен И (х) = по + а,х+... +а„,хл — ' Е Го (х) бу решением сравнения (4.3) в том и только том случае, когда ( а„..., а„,) является решением системы линейных уравнен (записанной в матричной форме) !:Кв (а,, а,, ..., а„,)В = (а,, а,, ..., а„,).

(4 Это следует из того факта, что равенство (4,5) выполняется тогй~,: и только тогда, когда л — ! л — ! л-! И(х) = ~' аух! = ~~ ~~ агЬых! == 4.! 1=о !=о ь=о л — 1 : — ~~ а,хго == И(х)о(шод1(х)). г=о Систему (4.5) можно записать в следующей эквивалентной формч:", (а,, ад, ..., а„,)( — Г) = (О, О, ..., О), (4.б „ где !' — единичная пхи-матрица над г„. Согласно доказанном,', выше, однородная система (4.6) имеет дь решений. Это означает.

что размерность пространства решений ') этой сися!ими равна ') Это пространство называют также оннулируемым пространством нуль-просп!раненном матрицы й — l. — Прим. перса. 4 1. Разложение миогочлеиои иад малыми иоиечиыми полями 19! е числу различных нормированных неприводнмых делителей „огочлена 1, а ранг матрицы  — 1 равен и — й. Поскольку постоянный многочлен Ь, (х) = 1 всегда является решением сравнения (4.3), то соответствующий ему вектор (1, , О) всегда является решением системы (4.6), в чем можно :бедиться также и прямой подстановкой.

Кроме 'того, найдутся еше непостоянные многочлены И, (х), ..., Иа (х) со степенями, не превосходящими п — 1, такие, что соответствующие им и много»лену И, (х) векторы образуют базис пространства решений однородной системы (4.6). Поскольку все многочлены И, (х), ..., Ьа (х) непостоянны и удовлетворяют сравнению (4.3),то онн являются 1-разлагающими многочленами. При таком подходе важную роль играет отыскание ранга г матрицы  — 1. Как было отмечено выше, г = п — й; поэтому, найдя ранг г, мы тем самым находим число й = и — г различных нормированных неприводимых делителей многочлена 1.

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

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