Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 45
Текст из файла (страница 45)
А это позволяет судить о том, до каких пор нужно продолжать процедуру разложения. Ранг матрицы  — 1 обычно определяется приведением этой матрицы к ступенчатому виду с помощью элементарных преобразований ее строк и столбцов. Однако, поскольку мы хотим в то же время решить систему (4.6), целесообразно применять лишь преобразования столбцов, поскольку пространство решений этой однородной системы инвариантно относительно таких преобразований. Итак, мы допускаем следующие элементарные операции: перемена местами двух столбцов матрицы  — 1, умножение любого ее столбца на ненулевой элемент поля Г» и прибавление к любому ее столбцу другого столбца, умноженного иа любой элемент из Г . Ранг г матрицы  — 1 — это число ненулевых столбцов полученной матрицы ступенчатого вида.
Вычислив г, мы найдем число й = и — г. Если й = 1, то мы заключаем, что 1 — неприводимый многочлен над 1», и процедура на этом заканчивается. В этом случае единственными решениями сРавнения (4.3) являются постоянные многочлены, и пространство Решений системы (4.6) состоит лишь из векторов вида (с, О, ..., О), где с Е Е». Если же й ) 2, то мы берем 1-разлагающий базисный миогочлей И, (х) н находим наибольшие общие делители НОЛ (1 (х), Ие (х) — с) для всех с Е 7».
В результате получим некоторое нетривиальное разложение многочлена 1(х), даваемое ФормУлой (4.2). Если использование многочлена Иа (х) еще не "Риводит к разложению многочлена 1 на И сомножителей, то переходим к следующему )'-разлагающему базисному многочлену Ь, (х) и находим ИОД (а (х), Ь, (х) — с) для всех с Е 7» и всех нетривиальных делителей а (х) многочлена ! (х), найденйых по формуле (4.2) на первом этапе. Эта процедура продолжается до тех пор, Гл. 4.
Разложение многочленов на множители Х', +.х' +х' +х, +х' + х' +х' -1-х', +хе +ха д-хв +х" +Ха +хе +Х. пока мы не получим все Ь неприводимых сомножителей мн члена 1(х). Описанный процесс должен в конечном счете привести к хождению всех неприводимых делителей многочлена ) (х),, ствительно, если рассмотреть два различных нормирован" непРивоДимых ДелителЯ многочлена ) (х), напРимеР Гт (х) н Ге, то рассуждение, следующее за сравнением (4.3), показывает, для каждого /, 1 <1< Й, существуют элементы сц и с поля г'ч, такие, что выполняются сравнения Ь, (х) = — сл ( )т (х)), Ь, (х) =— .
с;, (щи гз (х)). Допустим, что сл — — сз, для 1 < / < Ь. Тогда, учитывая, что любое решенйе Ь (х) сравн (4.3) является линейной комбинацией базисных многочл Ь, (х), ..., Ьа (х) с коэффициентами из Кч, получаем, что для бого такого решения Ь (х) существует элемент с Е (г'ч, та что Ь (х) = с (шоб ), (х)), Ь (х) = — с(шот) ), (х)). Но рассужде ' которое привело к сравнению (4.3), показывает, что существ в частности, и такое решение Ь (х) сравнения (4.3), что Ь (хд' О (шоб г, (х)) и Ь (х): — 1 (шоб )з (х)). Полученное проти чие доказывает, что сп Ф см для некоторого 1, 1 < г' < Ь ( нее, для некоторого г', 2 < 1 < Ь, поскольку Ь, (х) = 1).
П многочлен Ь,(х) — стт будет делиться на )т (х), но не на Гв, ' Отсюда следует, что любые два различных нормированных: приводимых делителя многочлена ) (х) обязательно «отдел друг от друга (в указанном смысле) некоторым базисным и' членом Ь, (х). Этот алгоритм разложения многочлена 1, основанный на!" хождении 1-разлагающих многочленов (путем решения си (4.6) линейных уравнений) носит название алгоритма Ба кэмпа. 4.2. Пример. Разложим многочлен 1(х) = х'+ х'+ х4' + х'+ 1 над полем ге, применяя алгоритм Берлекэмпа. ' как НОД () (х), )' (х)) = 1, то многочлен ) (х) не имеет кратп, сомножителей.
Нам требуется найти вычеты одночленов по модулю )'(х) для д = 2 и 1 = О, 1, ..., 7. Это приводит к с дующим сравнениям по модулю 1(х): ха = — 1, х' х', хе ха, Хе х': — 1 х10— хза =— и т— н 1+х 4 ц Разложение многочленоа над малыми конечными полями !93 Поэтому 8х8-матрица В имеет вид О 0 0 0 0 0 1 0 0 О 0 0 0 ! О 0 0 0 О 0 0 0 1 ! 0 0 1 1 1 1 О ! 0 1 1 1 0 1 1 1 а матрица  — 1 имеет вид (0 0 0 0 0 0 0 0 1 0 О 0 0 0 1 0 1 0 0 0 О 1 0 О ! 0 0 ! 0 0 1 0 1 ! 1 О 0 0 1 0 1 ! 0 1 0 1 1 ! 0 1 Несложные вычисления показывают, что матрица  — 1 имеет ранг 6 и векторы (1, О, О, 0,0,0,0,0) и (0,1,1,0,0,1, 1,1) образуют базис пространства решений однородной системы (4.6), соответствующей матрице  — 1.
Зтим векторам соответствуют многочлены Иа (х) = 1 и И, (х) = х + х'+ х'+ х'+ х'. Вычисляя при помощи алгоритма Евклида НОД (1(х), И, (х) — с) для элементов с ~ Г„получаем, что НОД (1 (х), И, (х)) = х' + + ха -,'— х' -1- х + 1, ЙОД (1(х), Иа (х) — 1) = х' + х + 1. В итоге получаем следующее каноническое разложение многочлена 1(х): ! (х) = (ха + х' + х' + х + 1) (х' + х + 1). с ! Другой метод получения 1-разлагающих многочленов связан с построением некоторого семейства многочленов, в котором имеется по крайней мере один !'-Разлагающий многочлен. Пусть снова 1 'бозначает произвольный нормированный многочлен степени и > 1, не имеющий кратных сомножителей, и пусть 1 = 1, ... 1а— его каноническое разложение в кольце К, [х), причем бей (~э) = '= п~ для 1 < 1 С И. Если У вЂ” наименьшее натуральное число, ~~~ос, что хч" = х (шое[1(х)), то нз теоремы 3.20 получаем, что = НОК (и,, ..., па), при этом также нетрудно видеть, что У— "епень поля разложения Р многочлена ) над [р .
Рассмотрим многочлен Т ~ [с [х! вида Т(х) = х+ ха+ хчз+ ... + ха~ !3 За«, за 0 1 0 0 О О 1 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 О 0 0 1 1 0 О! Гл, 4. Разложение многочленов на множители )94 Положим Т; (х) =- Т (х') для ! ь- !)ч. Следующий результат казывает, что в рассматриваемом случае (когда многочлен Т( приводим в кольце !Гч 1х) и не имеет кратных сомножите среди многочленов Т, (х), 1 ( ! < и, найдется хотя бы о 1-разлагающий многочлен. 4.3. Теорема. Пусть многочлен без кратных сомножите ' Г ~ Тч (х! приводим в 1ч 1х1. Тогда (возведенных выше обоз ниях) по крайней мере один из многочленов Т;, 1 ( ! ( и —, является 1-разлога!ощим многочленом.
Доказан!гласи!во. Учитывая сравнения хв':-'- х (шог( Г (х)), видим, что каждый из многочленов Т; удовлетворяет уело Тг =: Т! (той 1). Допустим теперь, что для всех многочленов 1 ( ! ( и — 1, разложение многочлена Г', даваемое форму (4.2), тривиально (при Ь == Т;). Это означает, что существуют менты с,, ..., с„, ~ Г'ч, такие, что Т! (х): — с, (шот(Г(х)) ! = 1, ..., п — 1. Рассматривая с, == Гч' как элемент поля получаем сравнения Т (х'):=- с; (шоб ) (х)), !' = О, 1, ..., и — '' Для любого многочлена л — ! й(х) = Е а;х! 6 Г,(х! степени меньше и мы имеем тогда га†! л — ! л — ! Т(д(х)) =- Т ( ~н а!х')) =- ~ а;Т(х!) = ~„'а!сг(шог(Г(х)).
1 !=.О г=о Полагая л — ! с(д) = ~~ а;с; ~ Кч, г=-о получим Т(д(х)) = с(д) (шог(11(х)), 1 = 1, ..., я. (4, Так как М = НОК (и„..., п„), то по крайней мере одно из лых чисел М)п1, скажем Ж)пт, не делится ') на характерист полЯ Кч. ПУсть О! — коРень многочлеиа Г! из полЯ Разложении ' этого мйогочлена над г',. В силу теоремы 2.23 (и) существуеч) многочлен д! ~ Тч !х1, такой, что г(ея(а!) (бед()'!) и Тге,,у (дт(0!)) -= 1. (4 1 1!! 1т' х ') Так как НОД 1 —,, — ! = !. — Г!рнм. перев.
1 п, '"' пк1 к) Учитывал, что Р! =- )Гв (В!). — Прим. перж 4 1. Разложение миогочленон над малыми конечнымн иолнмн 195 р,виду того что и )~ 2 (по предположению), мы можем применить китайскую теорему об остатках и получить такой многочлен е ~ 1'ч (х! степени меньше и, что д = а, (вод),), и = 0 (тог(гз).
(4.9) Из (4,8) и (4.9) следует, что Тгг,дг (й(8з)) = 1, так что из теорем 2.23(1ч) и 2.26 получаем равенсч"во Тгл(9- (аг(8,)) = У(п,, где г" — поле разложения многочлена ~ над Ке. Из определений следа и элемента 8, вытекает, что Т (а (х)) = 1ч 'гв, (аког( 1з (х)). Однако второе сравнение в (4.9) приводит к сравнению Т (д(х)) = О (пзоб(з (х)), и, посколькУ число Фlп, как элемент полЯ г'и отлично от нуля, мы получаем противоречие с (4.7). Это противо- речие означает, что по крайней мере один из многочленов Т„ 1 4 ~' ( и — 1, является (-разлагающим. П 4.4. Пример.
Разложим многочлен ~ (х) = х" + х" + хга + хга + х" + хга + ха+ + ли+ х'+ха+ х'+х+ 1 Е Кз(х), Поскольку НОД (((х), 1' (х)) = хза + х'+ 1, то многочлен 1» (х) =- 1' (х)/НОД Д (х), 1' (х)) = х' + х' + х' + х + 1 ие имеет кратных сомножителей. Разложим (е (х) описанным выше методом, найди 1»-Разлагающий многочлен. ДлЯ этого бУДем пРиводить по моДУлю 1» (х) степени х, х', х', х', ..., пока не найДем наимень- шего натурального числа У, такого, что х'": — х(шог(~е (х)). а — 1 Для упрощения записи условимся многочлен ~' азх' обозначать 1=о и- и а бором (вектором) (ае, а„..., а»,) из его коэффициентов; в частности, (е (х) = (1, 1, О, О, 1, 1, О, 1). Подсчет нужных сте- пеней переменной х по модулю (а (х) упрощается, если заметить, что квадРат многочлена (пе, пз, ..., пе) по модУлю (е (х) совпадает (в векторной записи) с произведением вектора (ае, а„..., пе) "а квадратную матрицу порядка 7, образованную четными степе- "ями переменной х, а именно ха, ха, ..., х'з, приведенными по мо- дулю 1» (х).
Эта матрица получается из правых частей следующих сравнений (по модулю 1е (х)): х': — (1, О, О, О, О, О, 0), ха = (О, О, 1, О, О, О, 0); 13» Гл. 4. Разложение миогочлеиов на множители х4 — (О 0 0 0 1 0 0) х' : — (О, О, О, О, О, О, 1), х' =- (О, 1, 1, О, О, 1„ !), хто = (1, О, 1, 1, О, О, !), хзе : — (О, 1, О, О, 1, О, 1).
Произведя теперь с помощью этой матрицы последовательные ведения в кнадрат, получим (по модулю 14 (х)) "'Ъ, х = (О, 1, О, О, О, О, 0), ха ==- (О, О, 1, О, О, О, 0), х' =- (О, О, О, О, 1, О, 0), хз = (О, 1, 1, О, О, 1, 1), хаа =- (1, 1, О, 1, О, О, 0), хаз = (1, О, 1, О, О, О„ 1), х'4 ==- (1, 1, О, О, О, О, 1), х"3 : †. (1, 1, 1, О, 1, О, 1), х'и са (1, О, О, О, О, 1, 0), 1 х"' = (О, О, 1, 1, О, О, !), хтееа ге (О, 1, О, О, О, О, О). Таким образом, М = 10 и многочлен Т имеет вид Т(к) = — Т,(Х) = ~ Кы: — (1, 1, 1, О, О, О, 1)(ШО41)3(К)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
