С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 7
Текст из файла (страница 7)
Выясним сначала разложимостьПосколькуf(O)===f(1)ных делителей не и меет.===2, f(2)===1, тоf(x) .f(x) линей-2.4.(IIIпоток) Конечные поля69Проверим существование квадр атичных делителей :422f( x) = х + 2х + 2 = (х +ах+ Ь)(х + сх + d) =224323= х + сх + dx x + ах + асх + adx + Ьх + Ьсх + bd =423= х +(а+ с)х + (Ь +ас+ d)x + (ad + Ьс)х + bd.Отсюда21) с= -а и коэффициент при х есть b-a 2 +d =О;2) из bd = 2 следует, что либо Ь = 1 и d = 2, либоЬ = 2 и d = 1, т. е. в любо м случае Ь + d = 3 = О ;23) но тогда из п. (1) а = О , т.е. а = с = О и коэффициент при х равен О::::}противоречие.4Т.
о. полином f (x) = х + 2х+ 2 = О над IF3 неприводим.Теперь рассмотрим поле IF3 [х] 1(х 4 + 2х + 2) .44В нём f( x) = х + 2х + 2 =О , т. е . х = х + 1 =О , и3корни f (x) суть х, х , хВычислим х 9 и х 27 :4227932х,33.х = (х ) х = (х+1) х = х + 2х +х;х932=х22= (х ) = (х + 2х + х) = х + 2х + х22 433= (х + 2х + х) + 2х х + х =22333= х + 2х + х + 2х + 2х + х3333962+ х + х.Ответ: в поле IF3 [х]1(х + 2х + 2)4уравнение4f( x) = х + 2х + 2 =О33232имеет корни х, х , х + 2х + х, х + х + х.3Глава704. Решить уравнениеЕf(x)== хf( x)52.Конечные поля+х +12== О , где!F2[x].Решение. Посколькуf (О)==f (1)1, полином==f (х)линейных делителей не имеет.
Кроме того, легко устанавливается, чтохт. е .52232+ х + 1 == ( х + х + 1) (х + х ) + 1,полином f (х) не имеет и (единственного) квадратичного н еразложим ого делител я и , поскольку е г о степ ень равна5,то он неприводим.Рассмотрим теперь поле !F2[х] 1(х + х + 1) .2255В нём f(x) == х + х + 1 == О , т. е. х == х + 1 == О и5f( х )корнисутьВычислим х858и хх == х х == (х16====имеет корни х,3(1) f( x)Решение.Е5332+ х + 1) уравнение25f (х) == х + х + 1 == О242343х , х , х + х + 1, х + х + х +5. Решить уравнениех и х2 .42х.:2Ответ: в поле !F2 [х] 1(х(1)32х,+ 1 ) х == х + х == х + х +(xs)2 == (хз + х2 + 1)2 == х6 + х4 + 15434х х + х + 1 == ( х + х) + х + 143х + х + х + 1.xl6 ==3х,222х , х,2!F2 [x];5f (х)1;2== х(2) f( x)2+х+Е !Fз [х] ;1.1 == О , если(3) f(x)Е!F5 [x].d eg f(x) == 2 и поэтому f(x) имеет 2 корня .Полиномf (х)неприводим над!F2 ::::}его корни2.5.(IIIпоток) Конечные поля71(2) Полином f( x) приводим над lrз :хпоэтому2+х +1f (х)==х2-2х+1== ( х - 1) ,2над [Г 3 имеет корень 1 степени 2.(3) Полином f(x) неприводим над lr 5 ~ его корних и х5 .2.5Существованиеиединственностьполя GF(pп)Вычисления в мультипликативной группе расrFi.ширения поля.
Построим полеЕго можно представить как факторкольцо [Г 2 /( а( х) ) по л1обому (покане доказано!) из трех неприводимых над [Г 2 многочленов 4-й степени:Сделаем это, взяв многочлен а( х) == хБудем задавать элементыrFi4+ х + 1.наборами коэффициентов многочлена-остатка при делении на а(х) , записывая их в порядке возрастания степеней.П орождающим является элемент а == х, которыйзаписывается как ( О , 1, О , О ) .Вычислим степени а, сведя результаты в таблицу.Глава724а ==а+ 12. Конечные полястепень ааа2аз41 +а== а25а+ а == аа2 +аз== абх2хз(0, 1,о,(0,(0,о,1,О)О)о,о,1)(1 ' 1,(0, 1,о,О)О)1х(0,о,1,1,1)1)аз+ а+ 1== аз+ а 4 == аза4 == а 7 ( 1' 1, о ,2281 + а == а + 1 + а + а == а (1 , о , 1, О)2а+ аз== а 9(0, 1,о,1)2(1 , 1,(0, 1,( 1' 1,(1 , о ,(1 , о ,(1 , о ,1,1,1,1,О)4а + 1 + а == а + а == аа+ а2 +221 + а + а + аз == а + аз +1 + а 2 + аз == а + а 2 + аз +1 + аз == а + аз +1 == а +аз4аа4а44а==========10all12аа 1за 1415ао,1)1)1)1)о,О)И мея такую таблицу, можно очень просто производить ум ножени е.Пример 2.1 6.
Как найти (хз + х + 1) · (х 2 + х + 1) ?41. Перемножить, учитывая х == хсложно ...2.+1-можно, ноС помощы{) таблицы :•представляем многочлены в векторной форме и по нейхз-в виде степеней а:+х+12х +х+1<<> ( 1, 1, О , 1)---+> а*-<> ( 1, 1, 1, О) <>а7,102.5.(IIIпоток) Конечные поля73• перемножая, с учётом аа7 а 1 оа17==15==3== 1, получаем :а2==х2 .22Таким образом: (х + х + 1) · (х + х + 1) == х .Нахождение минимальных многочленов.а(х)-Пустьнормированный неприводимый многочлен надlrр·Для нахождения м.м.mfЗ (x)элемента(3 поляlrР [ х] /(а (х) ) вычисляем сопряжённые с ним элементы2(3Р, (3Р , . . . поля, пока на векотором шаге d окажется ,что• либо (3d == (3 , тогдаmfЗ (x) == (х- (3) · (х - (3Р) · ...
· (х - (3Pd-l)и deg mfЗ (х) == d - 1 ~ deg а( х) .• либо (3d == х , тогда mfЗ (x) == а(х)и degmfЗ (x) == dega(x);При мер2.17.2элементов хН айдём минимальные многочлены для+ х,х2поля4F == lr 2 [x]/ (xВ этом поле х4 == х1. (3 == хс2+ х.+ х + 1).+ 1.Вычисляем элементы , сопряжённые(3:222422(3 == (х + х) == х + х == х + х + 1,224224(3 ==(х +х+ 1 ) == х +х + 1 == х+ ) +х + )2== х + х == (3 .Глава742.Конечные поля2Т. о . м.м . mf:J (x) имеет 2 корни /3, /3 , его степеньравна2иmrз (x) ~ (х - /3) (х - /32) ~ х2+ (/32 + fЗ)х + /33.222f3 + f3 ~ (х + х + 1) + (х + х) ~ 1,223f3 ~ ( х + х + 1) (х + х) ~~ х4+ f3+ f3+ f2+ ~2 + Х~ (х+ 1) + хт. е . mf:J (x) ~ х2~ 1,+ х + 1.Заметим , что•коэффициенты перед степенями х могут оказаться только константы О или1,иначе-ошибка ввычислениях;•вданномслучаевычислен ийкоэффициентовможно было не проводить , т.
к. х 2 + х + 1 - единственный неприводимый многочлен 2-й степенинад2. /3rr 2·~ х+ 1.Элементы, сопряжённые с/3:/32 ~ х2 + 1,44f3 ~ х + 1 ~ х + 1 + 1 ~ х .Заметим, что многочлен а( х) ~ х4+х + 1примитивен ,т. е . является м . м . для х . Поэтому а(х) будет м . м . и дляэлемента/3 ~ х + 1: mf:J (x) ~ а(х) ~ х 4 + х + 1.Ясно, что а(х) является м .
м. также и для сопря2жённых с х элементов х , х , х/3самостоятельно).48(выразите их через(III поток) Конечные поля2.5.Существование поля75для всехGF(pn)n.pnуже показали, что любое конечное поле имеетментов (рпростое,-Теперьn -установимМыэленатуральное) .существованиенеприводимогонормированного многочлена f степени n над GF(p) ,откуда последует существование поля из G F (pn) какфакторкольца по идеалу(f) .Для таких многочленов над конечным полем справедлив аналог основной теоремы арифметики: каждыйнормированный многочлен разлагается на произведениенеприводимыхмногочленоводнозначносточноевклидавамкольцестью до порядка сомножителей.Доказа тельство . Действительно:•разложение намножителиводнозначно;•в случае кольца многочленов над полем обратимые элементы•выбор-старшегонеиулевые константы;коэффициента1однозначноопределяет сомножители .DСимволом( (n)) обозначим число нормированныхнеприводимых многочленов степени n над полем 1Fp.Лемма2.3.Ld · ( (d)) == Pn ·dlnДоказа тельство.
Занумеруем iприводимые==1, ... , ((п)) все не-нормированные многочлены степенисопоставим им формальную переменнуюfi,n ::::}nипроизвольному многочлену однозначно сопоставлен моном(многочлен степениn_j берётся в степени s _j):Глава762. Конечные поляr!.;81n . . . . ."1 '1JSr.; n"r 'причем'1'~n·s·~ J Jn.j=lП оэтому все нормированные многочлены перечисляются формальным бесконечным произведением00Пi,nLfi~n==Lfi~~nl· · · · · Ji:~nr(*)k=O(раскрыты скобки и бесконечное произведение записано в виде формального ряда).Сделаем замену переменныхf i,n == tn,которая делает все многочлены одной степени неразличимыми.П риведение подобных приведёт к тому, что :в правой части ( *) будет ряд от переменнойКоэффициент приtn в этомt.ряде равен числу нормированных многочленов степени п, т. е.pn:00Lpntn.n=Oв левой частиnвсе веприводимые многочлены степенидадут одинаковый множитель (сумму бесконеч-ной геометрической прогреесииtn)и(*)превращается вооПоформуле суммып рогреесии:со знаменателем((n))00бесконечнойгеометрической2.5.(IIIпоток) Конечные поля1Прологарифмируемкращаются,nн7711- pt•( <<->> в обеих частях равенства соd):L ( (d)) ln ( 1 - td)=ln ( 1 - pt) .dПродифференцируем по t ( << - >> в обеих частях равенства сокращаются) :dtd-lL ((d)) l- tdр=l- pt ·dСнова воспользуемся форм ул ой суммой геометрической прогреесии :L ((d))dtd- ltdkd,kУмножаем наL Pn+ltn.=nt обе части равенства:L d((d))td(k+l)d,k=L pntn.nРавенство коэффициентов при одинаковых степеняхtи есть утв ержде ние леммы.DСле ствия .1.Сущ еств о в а?-tu е 1-tеnриво ди.мых .м?-tогочле?-tов.Доказа тельс тво.
П ростая оценкаn((n))=n- lPn - L k . ((k)) ~ Pn - L Pkklnk=OГлава78==>доказывает, что ( (n))2. Конечные полярn-Оpn- 1> .р -1О ~ существует хотя бы одиннеприводимый (и нормированный) многочлен степениnn; более точная оценка- ~n ~2.Ср е днее.многочленов :число( (n))rvо((n)).неприводи.мъtхнормированныхpn1n.Доказательство. Переход к пределу приn ---+оо в полученной формуле .оТ.о .
веприводимые нормированные многочлены составляют приблизительнонов степенинад полемn1/n-Ioчасть всех многочлеIFP.Ещё одна формула для числа ( ( n)) веприводимых нормированных многочленах степениФунr.:ци.я МёбиусаJ.1(n)n над 1Fp.определена для всехесли примарное разложение1,изnnЕtN:состоит••четного числа различныхсомножителей;-1 ,J.1(n)если примарное разложениеnсостоит••из нечетнаго числа различныхсомножителей;О,иначе (примарное разложениене свободно от квадратов) .Н апример :J-1(1)== 1(по определению),J-1(6)== 1,2.5.поток) Конечные поля(IIIJ-L(2)J-L(3)J-L( 4)J-L(5)79== -1 ,== -1,== о,== -1 ,== -1 ,== о,J-L(7)J-L(8)J-L(9)J-L(10)==о,== 1.Основное свойство функции Мёбиуса:LJ-L(d)==dlnТео ема2.9== 1,n > 1.1,nО,•(формула Гаусса).((n))1=nJL(d)p~ .LdlnНапример:р == 2, ( (4)) == ~ [ J-L(1 )24+ J-L(2)2 + J-L( 4)2 J2==р == 2, ((5)) ==р == 3, ((6)) ==tt[J-L(1)25~ [24+ J-L(5)2 J63==-22+оJt [32 -[ J-L(1)3 + J-L(2)3 + J-L(3)322]== 3;==6;+ J-L(6)3 J==== 116.Докажем теперь, что любые два поля с одипагх;овъtмчислом элемептов изоморфпъt.Тео ем а2.1 О.ПустъmQ (х) -члеп элемепта а Е п=-; иТо гда полеd -минималъпый многоего степепъ.[Fp [x]/(mQ(x)) изоморфпо подпол?<J [F~,поро;нсденпому степенями а.80ГлаваДоказа тельство .
Степениапринадлежатпространству с базисом 1, а, а 2 ,ляется подполем поля2. Конечные поляd-мерномуad- l , которое яв. . . ,r;, поскольку замкнуто относительно сложения и умножения и содержит О и2.61.оЦиклические пространстваДалеебудем рассматривать кольцомногочленовR == lrp[x]/(f) по модулiо главного идеала (!) возможно приводимого многочленаЕслиfнеприводим , тоЕflrp[x] .поле и этот случай ужеR-рассмотрен. Но в л1-обом случаеR -векторное пространство над [FР т. е .
совокупность многочленов степени меньшейdeg f .(! ) == { t · flrp[x]/(f) == { (j),g == (!)},tЕ [FР [х] ;g, h, . . . } ,+ g'degg, . . . < degf.. . ..Нормированный делитель порождающего элемента идеал аТео ем а2.11. Пустъ ер -гнеприводи.мыu гнор.мировагнгныu .мгногочлегнi поторыu делит1)f.Тогдасовопупгностъ всех въtчетовi пратгных ер, образует идеал в х:олъце плассов вычетов по .модулюIVJdef {t . ер }<J[Fp[x]j(J).f:2.6.(IIIпоток) Конечные поля<р -2)еди'Нсmвен/Н/ЫU в81'Нор.мирова'Н'Н'ЬlU .м'НогоI<prчле'Н минимальной степени .Доказательство.и, v, <рЕ<р==ао~ deg fk == deg <р1Fp [x],+ а1х + ... + ak-lXk- 1+хk,f ==фср.1. Проверим, что I 'P -идеал в кольце 1Fp [x]/(f).1.g Е I<ph Е 1Fp[x]/(f),-ghС== U<ph == vg == VU<pg**h Е I<p .2.-g == U<ph == V<p2.П окажем, что в<р==аонормированныхk==I<pнет других, кроме+ а 1 х + ... + ak- l хмногочленовk-l+хстепени,kменыпейdeg <р .Пустьg == и<р*degg ==т~ degcp == k.DГлава82Тео емаПустъ2.1 2.poвannъtuделителъ2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
