Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 47
Текст из файла (страница 47)
Заметим, что в контексте, связанном с разложением мпогочленов, мы будем считать порядок д конечного поля Гч «большима, если он существенно больше степени разлагаемого миогочлена. Пусть снова )" — произвольный нормированный многочлен степени и из кольца ге (х), разлагающийся в произведение й различных нормировайных неприводимых сомножителей над полем 1'ч. Допустим, что многочленй ~ Г (л) удовлетворяет условиям й' =- й (той )) и О ( г(ей (й) ( л, так что он является Г- разлагающим многочленом.
Поскольку различные наибольшие общие делители нз правой части формулы (4.2) взаимно просты, то ясно, что не более й из них могут быть отличны от 1. Задача с зстонт в том, как а рг(оН охарактеризовать те элементы с ~ Кч, для которых НОД () (л), й (л) — с) чь 1. Одну из таких характеризацнй можно получить, применяя теорию результантов (см. определение 1.93 и последующие замечания).
Пусть )г (Г(л), й (х) — с) — результант многочленов Г (х) и й (х) — с, где в качестве формальных степеней берутся степени этих многочленов. Тогда НОД Д (х), й (х) — с) ~ 1 в том н только том случае, если )с(((х), й(х) — с) = О. Так мы приходим к рассмотрению функции Р (у) = )г (( (х), й (х) — у), которая, очевидно, является многочленом степени, не большей п, относительно переменной у (учнтывая представление результанта з виде определителя). ясно, что НОд (1 (л), й (х) — с) ~ 1 в том и только том случае, если элемент с является корнем многочлена Е (д) из поля Кч.
й(иогочлен г (у) можно найти непосредственно из его определения; для этого потребуется вычислить определитель порядка не более чем 2п — 1, элементами которого являются либо элементы "' поля гч, либо линейные многочлены от у с коэфФициентами из ге Однако во многих случаях предпочтнтельнее другой способ, состоящий в следующем. Выберем и + 1 различных элементов га с», сн из Гч и поДсчитаем РезУльтантыг; = )г (1 (л), й (л)— с~), 1 = О, 1, ..., а. Тогда тот единственный многочлен г" (у) степени не пРевосходащей п, длЯ котоРого г (с) = гп 1= О, ", и, можно получить с помощью интерполяциоиной формулы 202 Гл, 4. Разлонгение многочленон иа множители Лагранжа (см. теорему 1.71).
Этот метод имеет еще то преимущ ство, что если какие-либо элементы г~ равны нулю, то мы авто тически получаем корни многочлена Р (у) из поля Кч. Во всяк случае вопрос о выделении тех элементов с Е Кч, для которм НОД (7'(х), Ь (х) — с) ~ 1, теперь сводится к вопросу накожд ния корней некоторого многочлена в поле 1'ч. Вычислитель аппарат для решения этой проблемы будет развит в следующ ' параграфе.
4.7. Пример. Разложим многочлеи 7 (х) = х' — Зха + 5х' — 9х' — 5х'+ бх + 7 над полем Геа. Так как НОД (7' (х),)' (х)) = 1, то многочлен 7 (х) не имеет кратных сомножителей. Прим ' няя алгоритм Берлекэмпа, найдем степени хем по модулю 7 ( для ! = О, 1, ..., 5. Это приводит к 6 х 6-матрице — 3 0 — 10 9 2 — 9 О 0 0 0 0 0 5 — 1 — 1 8 — 3 — 1Π— 10 10 9 0 1 — 9 0 7 9 — 9 10 — 11 11 0 — 4 7 6 2 — 3 0 — 10 9 2 — 10 Приведение этой матрицы элементарными преобразованиями стол,' цов к ступенчатому виду показывает, что ранг г матрицы В— ранен 3, так что многочлен 7' имеет й = 6 — г = 3 различи нормированных неприводимых сомножителай над полем е еа. Баз.
пространства решений однородной системы (4.6), соответствующ матрице  — 1, задается векторами Ь, = (1, О, О, О, О, 0), Ье ., = (О, 4, 2, 1, О, 0) и й, = — (О, — 2, 9, О, 1, 1), которые соответству многочленам Ь, (х) = 1, й, (х) = х' + 2х' + 4х и Ьа (х) = х' 1 0 0 О 5 0 — ! 8 — 10 10 10 0 0 7 9 — 8 11 0 — 4 7 так что матрица  — 7 имеет вид 0 0 — 3 — 10 1 — 9 10 — 11 7 2 4 2, Разложение многочленов над большими нонечнммн полями йбз 1- х' + 9хя — 2х. Возьмем теперь ~-разлагакзщий рассмотрим многочлен от у Р (у) =- Р (7 (х), Ьа (х) — У) = многочлен Ь, (х) 1 — 3 5 — 9 0 1 — 3 5 0 0 1 — 3 1 2 4 — у 0 1 2 4 0 0 1 2 О 0 0 1 0 0 0 0 0 0 0 0 — 5 6 — 9 — 5 5 — 9 0 0 — у 0 4 — у 2 4 1 2 0 ° 1 7 0 0 6 7 Π— 5 6 7 0 О 0 0 0 О О 0 0 — у 0 0 4 — у 0 2 4 — у так что многочлен ) (х) делит произведение П (Ь (х) — с).
аеас Введем в рассмотрение многочлеи 6(у) = П (у — с). аес 9тот определитель можно вычислить непосредственно, и мы полу- чим Е (у) = у' + 4у' + Зу' — 7у'+ 10у' + 11у + 7. Поскольку многочлен ) имеет три различных нормированных неприводимых сомножителя в кольце Гез !х), то, как отмечалось выше, много- член г (у) может иметь не более трех корней в поле газ. Применяя либо один из методов, рассматриваемых в следукзщем параграфе, либо метод проб и ошибок, находим эти корни, равные соответствен- но 2, — 3 и 6.
Далее, НОД (1 (х), Ь (х) — 2) = хз — х -1- 7, НОД() (х), Ь, (х) + 3) = х — 4, НОД(7 (х), Ьз (х) — 6) = ха +. 2хз -+ 4х — 6, так что каноническим разложением многочлена ((х) в кольце ; зз 1х) я~ля~тон ~ (х) = (х — 4) (х' — х + 7) (хз + 2х'+ 4х — 6). () Другой метод характеризации тех элементов с поля !г"„для которых нужно подсчитывать НОД (Г (х), Ь (х) — с) в формуле (4.2), основан на следунзщих соображениях.
Пусть сохранены те же обозначения, что и выше, и пусть С обозначает множество всех тех с ~ !г'ч, для которых НОД (Г(х), Ь (х) — с) Ф- 1. Тогда из (4.2) следует, что 1(х) = П НОД(1(х), Ь(х) — с), (4,14) гас 204 Гл. 4. Разложение многочленов на множители Тогда миогочлеи 1 (х) делит 6 (й (х)), и миогочлеи б (у) можно оха- ' рактеризовать следующим образом. 4.8. Теорема. Среди всех многочленов д ~ 11' 1у1, таких, что 1 (х) делит д (й (х)), многочлен 6 (у) однозначно определяется тем, что это нормированный многочлен наименьшей степени. Доказательство.
Мы уже показали, что иормироваииый много-, член 6 (у) обладает тем свойством, что 1 (х) делит 6 (й (х)). Легко, видеть, что миогочлеиы д Е г'и 1у1, такие, что ) (х) делит д (й (х)), образуют ненулевой идеал кольца 1(ч 1у). По теореме 1.54 этот идеал является главным идеалом, порожденным некоторым одно- зиачио определенным иормироваииым миогочлеиом 6, ~ Гч (у1. Это зиачит, что миогочлеи 6, (у) делит 6 (у), так что 6,(у) =- П (у — с) ебс, для некоторого подмножества С, множества С. Следовательно, 1(х) делит б, (Ь (х)) = П (Ь (х) — с), и, значит, ее с, 1(х) =- П НОД(~(х), Ь(х) — с). е ес, Сравнение с (4.14) показывает, что С„= С. Поэтому 6„(у) = = 6 (у), и теорема доказана.
П: Этот результат можно использовать следующим образом. Пусть; т — число элемеитов множества С. Тогда запишем ж 6(у) = П (у — с) = ~~ Ь~у/ сес у=о с коэффициентами Ь, Е Г . Поскольку ) (х) делит 6 (й (х)), то мы ' получаем ~ Ьзй(х)~ = 0(шоп1(х)). Так как Ь = 1, то это сравнение можио рассматривать как иетривиальное соотношение линейной зависимости иад полем К, связывающее вычеты по модулю ) (х) миогочлеиов 1, й (х~, ';: й (х)',, Ь (х)'".
Согласно теореме 4.8, если произвести нормиро- ' вание так, чтобы Ь = 1, то такое соотношение линейной зависи; мости определяетсяоднозначно; поэтому вычеты по модулю 1(х) 1 миогочлеиов 1, Й (х), Ь (х)', ..., Й (х) — ' линейно иезависимы иад:. Г . Ограничение т ~ Й (где Й определено в начале параграфа) вы- '' текает из (4.14). Поэтому миогочлеи 6 можно найти, если приводить по модулю 1 (х) степени миогочлеиа Ь (х): 1, Й (х), Й (х)', ..., пока ие найдем, $ 2. Раэложенне многочленов нел оольшнмн конечными нолнмн 205 ту наименьшую степень й (х)" этого многочлена, которая линейно зависит (над полем ге) от предыдущих степеней.
Коэффициенты этого первого соотношения линейной зависимости в нормированной форме (т. е. с коэффициентом 1 при Й (х) ) и являются коэффициентами многочлена 6. При этом мы знаем, что для нахождения этого соотношения линейной зависимости требуется рассмотреть лишь степени многочлена Й (х) не выше л-й, где число л можно получить из алгоритма Берлекэмпа. Элементами множества С являются корни многочлена 6, лежащие в поле г ч, и только они. Этот метод, сводящий проблему нахождения элементов множества С к задаче отыскания корней некоторого многочлена в поле гч, носит название алгоритма Цассенхауза. 4.9.
Пример. Рассмотрим снова тот же многочлен 1 (х) = = х' — Зх'+ 5х' — 9х' — 5х'+ бх + 7 Е Гээ [х), что и в примере 4.7. С помощью алгоритма Берлекэмпа мы уже нашли число его неприводимых сомножителей й, равное 3, и 1-разлагающий многочлен и (х) = х'+ 2х'+ 4х ~ Гээ [х!. Применим теперь алгоритм Цассенхауза для нахождения множества С тех элементов с Е Гээ, для которых ИОД () (х), й (х) — с) ~ 1. Мы имеем Ь ( ) = х'+ 2х'+ 4х (пюд) (х)), И (х)' = 7х' + 7хч + 2х' — 2х' — бх — 7 (шог[ 1 (х)), так что ясно, что й (х)' не зависит линейно от 1 и а (х). Поскольку число т элементов множества С не превосходит А = 3, то степень л (х)' должна быть наименьшей степенью многочлена Ь (х), которая линейно зависит от предыдущих степеней. Имеем й (х)э = — — 11хэ — !1хл — х' — 9х' — 5х — 2 (шоб 1 (х)), и искомая линейная зависимость такова: й (х)э — 5й (х)э + 11й (х) — 1О = 0 (шод ) (х)), следовательно, 6 (у) = у' — 5у' + 11у — 10.
Теперь, применяя либо методы следующего параграфа, либо метод проб и ошибок, находим, что корнями многочлена 6 в поле [1'ээ являются элементы 2, — 3 и б. Каноническое разложение многочлена 1 в Гээ [х) находится так же, как в последней части примера 4.7, П Приведем еще один метод, который основан на применении матриц из многочленов. Хоть его схема более сложна, но зато он представляет больший теоретический интерес. Под матриЧгй из миогочлеиов мы будем понимать матрицу, элементами которой являются многочлены из кольца Гч [х[.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
