Р. Лидл, Г. Нидеррайтер - Конечные поля. Т. 1 (1988) (1127099), страница 46
Текст из файла (страница 46)
!=о Поскольку многочлен Т, (х) не сравним с константой по моду „ го (х), то он является 13-разлагающим многочленом. Нахо НОД (Го (Х), Т, (Х) — С) дпя ЗНаЧЕНИй С = О И С = 1: НОД ф, (х), Т, (х)) = НОД «1, 1, О, О, 1, 1, 0„1), (1, 1, 1, О, О, О, 1)) =- ха ! х4 1 ха + ха НОД (1, (х), Т, (х) — 1) = НОД «1, 1, О, О, 1, 1, О, !),: (О, 1, 1, О, О, О, 1)) = = х'+х+ 1, и по формуле (4.2) получаем 13 (х) = (х' + х' + ха + к'+ 1) (х' + х + !). Второй сомножитель, очевидно, неприводнм в Те (х). Поскол число У .— — 10 является наименьшим общим кратным степ 4 ц Разложение многочленов над малыми конечными полями !зт „еприводимых делителей многочлена /а (х), а любое нетривиаль„е разложение первого сомножителя привело бы к значению У, тличпому от 10, то первый сомножитель тоже неприводим в Ка (х).
теперь остается разложить многочлен НОД (/(х), ~' (х)) = — хга -1- х" + 1. Нетрудно заметить, что х" + х'+ 1 = (х'+ , ха+!)', причем многочлен ха+ ха+ 1 делится на неприводимый делитель к'+х+1 многочлена /а (х), так что х'+ ха+ 1- 1 = (х'+ х+ !) (х' + х + 1), где многочлен ха + х + 1 тоже иеприводим над га (х!. Окончательно получим такое каноническое разложение многочлена / (х) в Га [х): / (х) = (х' + х' + ха + х' + 1) (ха + х + 1)' (х' + х + 1)'.
( ) Следует, однако, заметить, что, вообще говоря, /-разлагающие многочлены вида Т1 могут не привести к полному разложению миогочлена /, поскольку они неспособны отделить те неприводимыс делители /, многочлена /, для которых число /у/пг делится на характеристику поля Гч. В таком случае обычно сначала с помощью /-разлагающего многочлена Т; находят частичное нетривиальное разложение многочлена /, а потом ищут новые Т, для каждого из полученных сомножителей. Так в конечном счете получают полное разложение многочлена /. Но существует модификация изложенного метода, когда вместо многочленов Т; строятся связанные с ними многочлены /сь которые способны отделить все неприводимые сомножители много- члена / сразу. Предположим (без ограничения общности), что /(О) ~ О. Пусть огб (/(х)) = и, так что/(х) делитдвучлен х' — 1.
Поскольку многочлен / (х) не имеет кратных сомножителей, то на основании следствия 3.4 и теоремы 3.9 числа е и д взаимно просты. Пусть 1 — целое неотрицательное число; обозначим через т, наименьшее натуральное число, удовлетворяющее сравнению хгч ': — х' (тси) /(х)). (4.10) Пусть теперь я;()= '+ "+ ' +'''+ -- многочлен над К . Поскольку сравнение (4.10) эквивалентно сравнению (4.11) /4 ~: — !(юоде), которое в свою очередь эквивалентно сравнению д ~ =: 1 (тос1 (е/НОД (е, 1))), то отсюда следует, что число и, является показателем, которому принадлежит число д по модулю е/НОд (е, Гл.
4, Раэложеиие миого»левов иа миожители !). Сравнивая определения многочленов Т! и Иг, легко устав ливаем '), что Т! (х) =: — ')г! (х) (шог(((х)). н Ясно, что для всех ! справедливо сравнение г»1 = И! (шой, так что многочлены Й! можно использовать вместо Ь в форму'' (4.2).
Покажем теперь, что многочлены )г! обладают указанн " выше свойством. 4.5. Теорема. Пусть приводи.иый над полем Е» нормирован многочлен (" не имеет кратных сомножителей, й пусть ( (О) ~ и огд (1) = е. Тогда, используя вместо Ь (х) в формуле (4,2) м а жг-! члены )1! (х) =- х! + х!»+ х!" + ... + х'» ', 1 «! ~ е — а' где числа т, определяются условием (4.10), можно отделить неприводимые сомножители многочлена (, е — ! Доказательство. Пусть Ь (х) = ~агх! ~ 1'» (х) — реше а=е сравнения Ь (х)» ге Ь (х) (шод (х" — 1)). Если рассматривать дексы коэффициентов а; как вычеты по шод е, то ввиду взаимн е †! простоты чисел о и е получаем сравнение Ь (х) г— в Е а! г=е (шод (х' — 1)), так как при ! = О, 1, ..., е — 1 числа и) пр гают полную систему вычетов по шой е.
А поскольку Ь (х)»' ' е — 1 = ~ а,хг»„то г-о е — 1 е — 1 2' а!к!а = ~ а! х!»(шой(хе 1)) г=-о г=.о Рассматривая здесь показатели как вычеты по модулю е, мы внл дим, что соответствующие коэффициенты равны. Значит, а! ~' = а„для всех г, так что для всех ! выполняются равенства а! = а!» — — а;„* = ..., Поскольку т; — наименьшее натуральное ч ело, для которого имеет место сравнение (4.1!), то Ь(х) = ~'„а!)с! (х) (шод(х' — 1)), где множество У содержит по одному представителю от каждо класса эквивалентности при следующем определении отношенн' эквивалентности —: для !'„га (- 7 считаем, что г, г, тогда ж! — ! и — ! .
м~! И$ ! /.!-ж; ') Так как )(! (х)» = ~ х!» ' = ~~ '(х!» )» =- ~' х!» !=о (=о г=! Я! (х) (слог( 1 (х)). — Прим. иерее. 4 1, Разложение многочлеиов над малыми конечными полями 199 только тогда, когда имеет место сравнение 1, = (ад' (шоб е) для некоторого ( =- О. Таким образом, для подходящих элементов ') Ь;Е1ч в — ! Ь (х) = — ~ Ь1Р~ (х) (тое((х' — 1)).
(4.12) с=о Пусть теперь 1, (х) н !а (х) — два различных нормированных неприводнмых делителя многочлена 1 (х) (а следовательно, н двучлена х' — 1). Согласно рассуждению, которое привело к сравнению (4.3), существует такое решение Ь (х) Е Г, (х! сравнения Ь (х)' = Ь (х) (шоб (х' — 1)), что беЯ (Ь (х)) < е н прн этом Ь (х) =: О (той ~а (х)), Ь (х) = 1 (той) (х)). (4.13) Поскольку Рч = Р1(той ~), то нз рассуждення, следующего за сравнением (4.3), вытекает существование таких элементов см, г,, '- г"ч, что Р, (х) = сн(апой~,(х)) н Р, (х) =— см(шод (в(х)) длн всех 1, О ~ 1 ~ е — 1.
Если для всех этих 1 имеет место равенство сн = с;а, то нз (4.12) следует, что для некоторого с Е имеют место сравнения Ь (х) = с (щи ~, (х)), Ь (х) г— н с (шод (а (х)), но это противоречит сравнениям (4.13). Поэтому должно быть г„~ см для некоторого 1, О ( 1 ~ е — 1 (точнее, для некоторого 1, 1 < ( ( е — 1, так как Р, (х) = 1). В таком случае многочлен Р, (х) — сн будет делиться на ~, (х), но не на (а (х). Следовательно, используя этот многочлен Р, (х) вместо Ь (х) в формуле (4.2), мы отДелим ~, (х) от (а (х).
() Из доказательства теоремы 4.5 видно, что все непрнводнмые делители многочлена ( могут быть отделены многочленамн Р;, где 1 пробегает ненулевые элементы множества 7. Однако для нахождения множества У требуется знать порядок н многочлена ~; пРямой же подсчет числа е (т. е. без использования канонического Разложения многочлена Д), как правило, чересчур громоздок. Такая проблема не возникает в следующих двух частных случаях — двучлена 1 (х) = х' — 1 н е-кругового многочлена 1 (х) = ()е (х), поскольку в обоих этнх случаях, очевидно, огд (х' — 1) = .
' огб (Я, (х)) = е. Оказывается, что многочлены Р; очень удобны длн разложения таких двучленов н круговых многочленов. 4 б. Пример. Найдем каноническое разложение кругового многочлена Яаа (х) в кольце Га (х). Согласно теоРеме 3.27, (хаз — 1) (ха — 1) (еаа (х) = = х" — х" + хва — х" + х" — хм+ х"— — х'е + х' — ха + ха — ха + 1. 1 У.. = О, ° 1. — П, Гл. З. Разложение многочленов на множители Рассмотрим теперь многочлен гсг (х) = х + хз + х' + х" +х'з„" + х"'. Ввиду того '), что х":= — 1 (щос! !гзз (х)), получаем, !ст (х) == О (тоб Язз (х)), так что Иг не является Язз-разлагающ многочленом. Переходим к следующему многочлену гсз (х) = хз + х'+ х".
Для него получаем НОД (Язз (х), йз (х)) =. х' — хз + 1, НОД Язз (х), !сз (х) + 1) = хз + х' — х' + 1, НОД (4з (х), йз (х) — 1) — х" + хгз — х + х + х + х +1 — — д (х), так что из формулы (4.2) следует равенство д (х) (хз хз + 1) (хз + Х4 хз + 1) й (х), Согласно теореме 2.47 (Н), круговой многочлен Дзз (х) в кол 1з [х) разлагается в произведение четырех неприводимых сом жителей степени 6.
Так что остается только разложить мног' член п(х). Поскольку Яз (х) = х'+ х'+ х" + хж + хма; + х"' = — О (щод Щз (х)), переходим к следующему многочл тгз(х) = х'+х" +х". Заметив, что хгз =— — х'з+х' — хз — ха — х' — 1 (шод д (х)) и х": — — хгз (щод д(х)), получим, что !сз(х) = — хтз+ хз — хз — х' — 1 (щос(я(х)). Поэтому НОД(п (х), !с„(х)) = НОД(д (х), хзв+ х' — х' — х' — 1) НОД (д (х), !2, (х) + 1) = НОД (д (х), х" + х" — х' — х') = = хе — х'+ х'+ 1, НОД (д (х) йз (х) 1 ) НОД (и (х) хте + хз х хз + 1) =ха ха+ 1 Таким образом, искомое каноническое разложение многочле ' 1„)зз (х) имеет вид ()зз(х) = = (х" — х'+ 1)(х'+ хз — х'+ 1)(х' — х' + х'+ 1)(х' — х' -)- 1). 5 2.
Разложение многочленов над большими конечными полями Если Кч — большое конечное поле, т. е, число д велико, практическое применение методов предыдущего параграфа новится затруднительным. Хоть мы и можем, затратив определе, ') Так как к'е+ ! = (Хгл — !)~(лтз — !) содержит все первоооразные о2-а степени из !. — Прим. нерее. 4 2, Разложение многочленов нал большими конечнммн полнмн 20! ные усилия, найти Г-разлагающий многочлен, однако прямое использование основной формулы (4.2) становится уже нереальным, „ак как оно требует подсчета д наибольших общих делителей. Поэтому для того, чтобы сделать возможным использование (- разлагающих многочленов и для больших конечных полей, необходимо изыскать пути сокращения числа элементов с Е Кч, для которых в формуле (4.2) нужно подсчитывать наибольшие общие делители.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
