С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 6
Текст из файла (страница 6)
.м. дл.я эле.мептатак;оui чтоf ((3)=== О . Тогдаполе(3 i а f (х) f (х) делитсяГалуа.м'ногочлепна mrз (х).Доказательство. Разделимf(x)===u(x) · mrз (x)f (x) на mrз (x) с остатком :+ v(x), О ~ degv < degmrз (x) .Подставляя в это равенствоО ===f ((3)===(3вместо х, получаемu(f3) mrз ((3) +v ((3)"V'===v ((3) ,",1=0т. е .(3 -mrз (x) икореньv(x), чтопоэтому v(x)противоречит минимальностиО.о2.4.(IIIпоток) Конечные поля57Сле ствие. Дл.я паждог о элемента пол.я существуетне более одного м.м.Доказа тельс тво . Пусть минимальных многочленов два.Они взаимно делят друг друга, а значит, различаютсяна обратимый множитель-константу.Поскольку минимальный многочлен нормирован,эта константа равнат. е.
данные многочлены совпа1,дают.оУтве ж ение2.7 . Дл.я к;аждого эле.ме?-tта {3 пол.я IF~существует .м ..м .дитn: deg т{З(х)m f3 (х)~ n.и его степепъ не превосхоДоказа тельство . Рассмотрим следующие элементы поляIF~: 1, {3, {32, . . . ,{3п - их n+ 1 штук , а размерность IF~как векторного пространства равнаn=?эти элементылинейно зависимы, т. е . существуiGТ такие не все равныеО коэффициенты со,=?... , Сп, чтосо 1 + с1fЗ + .
. . + cnf3n == О,{3 - корень многочлена f (х) == са + с1 х + . . . + CnXn .Минимальным многочленом для {3 будет некоторыйнормированный неприводимый делительf (х).Далее будут доказаны ещё два свойства м.м.элемента{3m f3 (x)поля IF~:1.ffi(3 ( Х)2.Многочлен(хРп рсо{3Р2Х) .минимальный{3Pdegm13(x)-1{3 ' rз '' ...'{3 элементов IF~.для••с оnр.яж еn н ъtхГлава58Конечные поля2.Свойства многочленов над конечным полемПоле разлоDfсепи.я мпогочлепаменьшеерымf (х)1r;, n == minf(x)Ер асширение поля!Fp[x] !Fр,наинад которазлагается в произведение линейных множителей .Тео ема 2.4 (о поле разложе ния). Любой ненулевоu элемент пол.яxPn - l -F1r;==.явл.яетс.я гк;орпем многочлена1:n_ lхР-1 == ( Хгде { (31 , ...
, /3рп_ 1==}fЗ1 )-· . . . · (Х-(Зрп -l)F* , т. е. F - поле разложенияданного многочлена.Доказател ь ство .F * - циклическая групп а по ум ножению порядка pn - 1.Порядок ord а любого её элемента (== порядок циклической подгруппы (а)-по теореме Лагранжа) делит порядок группы .П оэтомуapn- 1 _1==pn - 1 == q · ord aaqoгda _1т.
е . а- корень xPn - l -==и(aoгda)q _1о,1.DСле ствие (тео рем а Фе рм а ) . Все элемепты пол.я1r;, nenисгк;люча.я нул.я, .явл.яютс.я гк;орн.ями мпогочлепа хР - х.Доказательство. Вынесем х за скобку:хРп -Х == Х ( хРп - l -1) .У второго сомножителя корнями будут все неиулевыеэлементы поля, а у первогоИными словами ,nхP-х.1r; --О.ополе разложения м ногочлена2.4.(IIIТео ем апоток) Конечные поля2о 5 о59В rх;олъце .многочленов над rх;онечны.м полем••(xn- 1) : (xm- 1) {::} n :т.Доказа тел ьство.•Пустьn ==тk . Сделаем заменуxm ==у, тогдаxn - 1 == yk - 1 и xm - 1 == у - 1.Делимость очевидна, т. к .
1 - корень yk - 1.••Предположим, чтоО<r <П оследнее/т, т.е.nn == km+ r,т, тогдавыражениезадаетрезультатделенияxn- 1 на xm- 1 с остатком, поскольку xmk- 1 делится на xm - 1 по доказанному выше.О статок xr - 1 =/= О в силу сделанных предположений .С ледовательно xn - 1 не делится на xm - 1.оТеорема даёт возможность раскладывать многочленыxn - 1при составныхn.Пример 2.12. Многочлен х 1 5 + 1 Е lr 2 [x] (гдедолжен делиться на х 3 + 1 и х 5 + 1.- 1 == + 1)Действительно,х15312+ 1 ==(х + 1 )(х5109+х +х +х + 1 )56== (х + 1) (х + х + 1).360Глава 2.
Конечные поляТео ем а2.б . Все веприводимые .многочле 'Н/Ы n-u cme'-'nпени из rFp[x] дел.ят многочлен хР-х.Доказательство .n ~ 1. Убеждаемся , что (х-а)(хР- х), где а Е [FP:поскольку аР ~ а, оба дан н ых многочлена имеюткореньn> 1.а.В ыбираем неприводимый нормированный м ногоf (х)членустепенино!1 ) и строим полеиз [FР [n] (пока не доказаn[Fр[х]/ (f(x)).В нём х- корень и своего м . м . f(x) , и xPn- 1 - 1.По свойствам м . м . xPn- l- 1 делится на f(x) .DПример2.13 (продолжение Примера 2. 12) .
Продолжаемразложение х 1 5 + 1 Е [F 2 [х] .4Поскольку 15 ~ 2 -1 , все неприводимые многочле16ны 4-й степени будут делителями х - х и , следовательно, х 15 + 1. Таких многочленов 3:443432х + х + 1, х + х + 1 и х + х + х + х + 1.И меем153443432х + 1 ~ (х + 1 )(х +х+ 1 )(х +х + 1 )(х +х +х +х+ 1 ).Замечаем , что 3 ~ 2 - 1, и поэтому все неприводи4мые многочлены 2-й степени будут делителями х - х3и , следовательно, х + 1. Такой многочлен только один :2х + х + 1.Окончательно получаем разложение х 1 5 +1 на нераз2ложимые над [F 2 многочлены:1Теорема 2.12.4.хпоток) Конечные поля(III15612+ 1 == (х + 1)(х + х + 1) хх (х + х + 1) (х + х + 1) (х + х + х + х + 1).443432Тео ема 2. 7. Любоu кеприводи.мыu де.л.ящиu xPn .мкого'Lt.лек имеет степекъ, ке превосход.ящуюДоказа тельс тво.xPn -х степениТогда FП устьерk.!Fр/ (ер) -defхk- lОбозначим химеем аРn- а==n.н еприводимый делительполе, которое рассмот-рим как векторное пространство над1' -х, . .
. 'х!FРс базисом.==а. Посколькуn.(хР - х) : ер, то в FО.Любой элементFвыражается через базис:k- lf3 ==Laiai .i=OВозведя обе части этого равенства в степеньчимk- lf3Pn ==Lf3 -полу-k- lLai a ii= Oт. е .pn,ai a i== /3,i=Oкорень уравненияхpn-х_ О-Итак , каждый элемент поляF является корнем ( *) ,но у ( *) не более pn различных корней, а F == pk;п оэтому n ;? k.о62ГлаваИтак,f(x)вопрос:Екакиеделят хР!F[x]Ответ: либоn-2.
Конечные полявеприводимыемногочленых?- степени n , либо (2) некоторый - степени < n и (3) других нет.(1)л1обойСледующая теорема позволяет находить все корнимногочлена, если известен какой-либо корень известен :достаточно возводить его последовательно в степени р .Тео ема 2.8 (свойство корней неприводимого многочлена). Если f3 %оре'Нъ 'Неnриводи.мо го .м'Ногочле'Настеnе'НиJ(x)p(3Р2f3 , f3 ,,(ЗРп- 1... ,изn!Fp[x] ,исчерпываюттосписо%эле.ме'Нтывсехnег оnop'Нeu .Доказательство.f (х),то (ЗР-l.Покажем , что еслиf3 -кореньтоже корень .П оскольку аР==а для всех а Е!Fр,то справедливо(ао + а1х + ...
+ akxk)P ==+ afxP + а~х Р + ... + a~Xkp ==== ао + а1 (хР) + а2(хР) + ... + ak(xP)k,2аь2т. е . для любого многочлена ср(х) Е!Fp[x]выполняетсяраве н ство( <р ( х) ) РОтсюдаJ(/3) ==1О==<р ( хР) .{::} J(f3)P ==(*){::} J(f3P) ==ОО иf3, (ЗР, ... , (ЗРп- - корни многочлена f (х).2. Осталось доказать, что все f3, (ЗР, ...
, (ЗРп- раз1личны , и тогда (многочлен степениnnимеет не болеекорней) можно утверждать , что найдены все корнимногочленаf (х).2.4.поток) Конечные поля(IIIl==Пр едположим, что (ЗР(ЗР63k,считая~lk.Далее ,по скольку(ЗРто (3 -корень уравненияП о Теоремет. е .l == kрk==xPn- k+l _1 -2.6 получаем n - k1==+lО.~~nl~k,и все вышеописанные корни р азличны .Корничленаn-k(3,f (х)(ЗР, (ЗР2степениn- l(ЗР, ... ,nовеприводимого много-называi{)Т сопр.яже:нны.ми и ясно, что они лежат в полеrFp[x]/ (f (x)).Нахождение корней неприводимого многочленаПр имер2.14.1.м ногочл е н аН айти корни неприводимого надf( x) == х4lF2+ х + 1.3Решение.
Один корень получаем немедленно : это х .П о только что доказанной теореме можно выписатьостальные корни в поле2х ,4х == х3+ 1,lF2[x]j(j(x)) :8х == х6+1Покажем, что, например, х 2 -==х32+ х + х.действительно корень f(x) : поскольку f(x ) == х + х 3 + 1 хнх 2 == х 8 +2686х + 1 и х == х + 1, то f (х ) == О.22. Решить4уравнениеО,f( x)ЕlF2[x] .Глава642.Решение. Убеждаемся , что многочлендим в1F2 [x] . Поэтому один его корень -Конечные поляf( x)непривох, и по доказанной теореме выписываем остальные в поле [F 2 [х] / (f (х)) :Покажите самостоятельно, что х 3реньдействительно кот. е. чтоf(x),3.
Решить-ур авнение2f( x) = х + 2х- 1 = О , где f( x) Е 1Fз[х] .Решение. Перебором элементов хубеждаемсяf( x) -Е 1Fз ={О,1, 2}веприводимый многочлен.2Но тогда в поле 1F3 [x]/ (х + 2х + 2) он имеет корни х3и х .Поскольку х 2 = -2х3+1=х+ 1, тох = х + х = 2х + 1.Убедимся, что 2х2f( x +x)=2+1-корень2( 2х+ 1) +х+ 1f( x) :=2= х + х + 1 + х + 1 = 3 · (х + 1) = О.2Ответ: многочлен f(x) = х + 2х- 1 Е 1Fз[х] имеет2корни х и 2х + 1 в поле [F3 [x]/ (х + 2х + 2).2.4.(IIIпоток) Конечные поляАлгоритмf(x)Енахождениявсех65корнеймногочленаlrp[x].f (х)1.
Разложитьна неприводимые произведение неприводимых многочленов:f (х)==91 (х) . 92 (х) . .... 9k (х) .2. Для каждого многочлена 9i (х), i == 1, k рассмотреть расширение lrp [x]/(9i (x)), в которомон будет иметь deg 9i корнейра,а,р2а, ... ,pdeg g,i - lа.3. Объединить все корни в одном общем расширении rr;, где n == н ок ( n1, . .. ' nk ).Пр имер2.15. 1.Решить уравнение4f(x) == 2х + х + 4х + 4 == О, где f(x) Е lrs[x].Решение.х32Вычисляемf (х)значениядлявсехЕlr 5 == {0, 1, 2, 3, 4 }: f( O) == 4, f( 1) == 1'f(2) == О и т. о .
х == 2 - корень f(x).Деля << уголком >> f(x) на f 1 (х) == х - 2 == х + 3,4233получим2х +х +4х +4 == (х+3) · (2х +4х+3) .Для удобства нормируем частное 2х + 4х + 3 : т.к.132- == 3, то вместо уравнения 2х + 4х + 3 == О можно3решать уравнение3f 2 (x) == 3 · (2х +4х + 3) == х + 2х + 4 == О .Перебором элементов х Е [Г 5 -366Глава2. Конечные поляf(O) == 4, f(1) == 2, f(2) == 1, f(3) == 2, f(4) == 1,3убеждаемся , что f 2 (x) == х + 2х + 4 - неприводимыймногочлен 2 .В поле [Г 5 [х] 1(х 3 + 2х + 4)255!2(х) == О будут х, х , х .корнями многочлена== -2х- 4 == 3х + 1:22253х == х (3х + 1) == 3х + х == 4х + 3 + х ==2== х + 4х + 3;х25 == (х5)5 == (х2 + 4х + 3)5 == xlO + 45х5 + 35 ==102102== х + 4(х + 4х + 3) + 3 == х + 4х + х .Вычисляем - с учётом х 31055(поскольку 4 == 2 == 1021 и 3 == 81 · 3 == 24~) .Найдём отдельно х 10 :xlo == (х5)2 == (х2 + 4х + 3)2 ==42223== х + х + 3 + 3х + 4х + х ==432== х + 3х + 2х + 4х + 4 ==22==:Ух + ~+ ~х + 3+ 7х + 4х + 4 == 4х + 2.Продолжаем:х251022== х + 4х + х == ~х + 2 + 4х + ~ == 4х + 2.4322Ответ: уравнение f (х) == 2х + х + 4х + 4 == О , где22f(x) Е IF5[x] имеет корни 2, х, х +4х+3, 4х +2 в поле3[F == IF 5 х] х + 2х + 4) (поскольку корень 2 Е F ).1(2.Решить уравнение8j(x) == х + х + х + х + 1 == 0, где j(x) Е [Г2[х] .242а если бы это был многочлен 4-й степени?2.4.(IIIпоток) Конечные поляРешение.67В таблицах веприводимых многочленов данный многочлен отсутствует.Подбором находим, чтоведение двух веприводимых над842х +х +х +х+ 1 == (х4"f 1 ( х)Уравненияразлагается в п роизf(x)IF 2 многочленов:34+ х + 1) · (х + х + х + х + 1) .2""vfl(x)== О и3f 2 ( х)== О ранее были решены: их корни соответственн о суть23х, х , х2332+ 1, х + х + хв поле F 1 == IF 2 [х] 1(х43+ х + 1)их, х , х , х32+х +х+1в поле F 2 == IF 2 [ х] 1(х4Степени обоих расширений поля32+ х + х + х + 1) .GF(2)совпадаюти поля F 1 и F 2 изморфны (пока не доказано!),т.о .
все 8 корней уравнения f (х) == О лежат в поле(==4)GF(24).Для запи си данных корней выберем представлениеF 1 поля GF(2 4 ) . Тогда запись корней 1 (x) == О останется без изменений , а корни 2 ( х) == О надо предстаffвить как элементыF 1.Приравнивая многочлены,порождаiQЩИе данныеполя, получим43х +х + 1 == х +х +х +х+ 1Ясно,432что при подстановкех~х+1 полученное равенство останется справедливым . Пр именим данную постановку для изоморфного п реобразования полейF1 н F 2.68Глава2.Конечные поляНаходим представления корней многочленаf 2 (x)вполе F1:х ~ х+ 1,2х ~ (х2+ 1) === х + 1,2333х ~ ( х + 1) === х + х + х + 1,22233х + х + х + 1 ~ (х + х + х + 1) + (х + 1)+2+ (х + 1) + 13х .:=:2Удостоверимся, что, например , х + 1 - корень f( x):f(x2+ 1)2(х + 1) +(х + 1) + (х + 1) +(х + 1)+ 1===28===(х162416+ 1) +43(х82+ 1) +82(х4+ 1) + х32===.6Очевидно х === х , х === х + 1 и х === (х + 1) === х + 1.453Поскольку х === х + х === х + х + 1, то22264383х === х + х + х === х + х + х + 1 и х === х + х + х .2Подставляя в выражение для f (х + 1) полученные2полиноми альные представления степеней х, получи м2f (х + 1)3=== ( х232+ 1) + (х + х + х + 1) + х + х === О.Ответ: многочлен f( x) === х 8 + х 4 + х + х + 1 Е IF 2 [x]333имеет корни х, х , х + 1, х , х + 1, х + х + х,343х+ 1 , х +х +х+ 1 в поле IF 2 [x]/(x +x + 1).222223.Н айти корень многочленаf(x)===х4+ 2х + 2===О Е IFз[x].Решение.