С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 8
Текст из файла (страница 8)
Конечные поля<рnеприводи.мыu nop.ми.мnогочлеnа fЕlrp[x] иdeg <р == k < deg f == n .Тогда идеал (<р) мерnасти n - k.век;торnое npocmpancmвo разДоказательс тво. Без доказательства.Циклическое пространство.цо вычетов по модулю•Пустьxn - 1.некоторым полемF.•Фиксируем некоторый базис•ТогдаV.p n ==rv== { ( ао, . . . , an- 1 ) ai-Будем изучать кольп-мерное векторное пространство надV-VDЕ F, iО , 1, . .
. , n==- 1}координатное пространство.Опр еделение2.4. Подпространство координатного пространства pn называется чик;лическ;и.м, если вместе с набором ( ао, ... , ап- 1) оно содержит циклический(ап- 1, ао,скиесдвиг...,сдвигивправоап-2)наэтогонабора,т. е.набор(а следовательно и все цикличе...Произвольноечислопозициивлевоивправо).В кольцеторноеlrp[x]j(xn- 1),пространство1' х, . . . 'хn-1•надрассматриваемом как векполемlrРимеетсябазис2.6.поток) Конечные поля(III83Циклический сдвиг координат в этом базисе равносилен умножению нат.к. в этом кольцеТео емаxn == 1.Пустъ2.13.подпространство полъrцаIТо гда!Fp[x]/(xn- 1).I -х:rципличеспое{:} I<J!Fp [x]/(xn- 1)Доказа тельс тво.•Если подпространствоI -идеал, то оно замкнутоотносительно умножения наи есть циклический сдвиг ==?•ПустьI -!Fpj(xn- 1)а это ум ножениеI -циклическое.циклическое подпространство кольцаиgЕТогда g · х, g · х 2 ,J....
-также принадлежатЗначит,g ·fмуидеал .I -х,ЕIциклические сдвиги, т. е .I.f,для любого многочленапоэтооПримитинные корни( т.е.корни изБыло по1).казана: любой многочлен с коэффициентами из!FРразлагается на линейные множители в некотором поле(разложения)Пусть!Fq-GF(q) ==1r; характеристики р,q == рп.поле характеристики р, в котором разлагается многочленxn- 1.Справедливо:Глава84• В lF q выполняется равенство2.Конечные поля1 == (xkxkp -nxn - 1-1 )Р,поэтому интересен случай, когдавзаимно просто с р : тогда у многочленакратных корней нет (он взаимно прост со своей производнойnxn-l ).•Равен ствоxn == 1означ ает, чтоord хnв циклической группе [F~.xn - 1 == О образуJот группуедини'Ц'Ьl - подгруппу в [F~ .Вывод : корни уравненияnopнeu степениизnЭта подгруппа также циклическая; её порождаiQщиеэлементыстепениназываiQТСЯпри.митивны.мипорн.я.миn.П одгруппа в циклической группе существуетпорядок делит порядок циклической группыlF q содержитn (q- 1).множители в полеGF(q) ==xn- 1её=? полегруппу корней из единицы степениЧтобы вернуться от разложенияiffn iffна линейныеп=-; (корни изжениFо на веприводимые множители в1) к разлополе lFр, нужнопонять, какие корни из единицы будут входить в веприf (х).водимый делительЕслиегоf3 -корень( сопр.яа+сённъtе)f(x),корнито (ЗР, (ЗР=?2и т.д .
- такжеколичество и степенимногочленов-неприводимых делителейxn - 1можнонайти, разбив [FP на орбитъt отображенияw н pwПр имерmod n .2. 18. 1. Рассмотрим ещё раз разложение многочлена х 15 - 1 н ад [F 2 . Относительно умножения на 22.6.(IIIпоток) Конечные полявычеты по модулю15 -{О ,851, ... , 14 } разбиваJотсяна орбиты :{ о} ,{ I , 2, 4, 8 }, { 3, 6, 12, 9}, { 5, 10 },{ 7, 14, 13, 11}Поэтому х•••151 разлагается в произведение-одного веприводимого многочлена степени1,одного неприводимого многочлена степени 2,трех неприводимых многочленов степени 4.Конкретно (разложение было раньше) :х1524+ 1 == (х + 1) · (х + х + 1) · (х + х + 1) ·44233· (х + х + 1) · (х + х + х + х + 1).232. Рассмотрим разложение многочлена х - 1 над IF 2·Относитель но ум ножения на 2 вычеты по модулт-о 23разбиваются на три орбиты:{O},{I, 2,4, 8, 16, 9, 18, 13, 3, 6, 12 },{ 5, 10, 20, 17, 11 , 22, 21, 19, 15, 7, 14 }Поэтому х231 разлагается в произведение одногонеприводимого многочлена степени 1 и двух веприводимых многочленов степени 11 .-Кольца многочленовlrp[x]и конечные поля: рез юме•Любая конечное целостностное кольцо являетсяполем.Глава862.
Конечные поля•Характеристика конечного поля•ЛIQбое конечное поле хар актеристики р состоитизq == pnэлементовnЕпростое число .-fN .• а Е { G F (q) "- О} =* ord а q - 1.•Мультипликативная группа поляся циклической: в нейGF(q) являетсуществует rp( q - 1) примитив:ных элементов (генераторов, элементов порядкаq - 1).Для нахождения самих генераторов нет эфф ективных алго ри тмов.•ЛIQбые два конечных поля, содержащих одинаковое количество элементов , изоморфны.- подполе• GF (pm)•ОдночленыввекторномGF (pn)-1 ' х,' ...==[Fp[x]базиснадкольцомn.Для каждого натур альногоновхn.n- 1про ст р ан стве[Fp[x]j(a(x) ) , dega(x)•х2<==? тnв кольце многочленад простым полем [FP имеются веприводимые (не имеющие несобетвенных делителей)многочлены .Кольцо[Fp[x] -кольцо с однозначным разложением многочленов на неприводимые .
Для нахождения веприводимых многочленов нет эффективных алгоритмов .• Идеала(х)(а ( х) ) ,Еные а(х).rFp[x]порождё:н:ныйсоставляютмногочленоммногочлены,крат2. 7.(IIIпоток) Конечные поля87• Фактор-кольцо IFР [ х] /(а (х)) является полем, еслии только если а(х) - неприводимый многочлен вкольце IFР [ х] .Еслипри этомdeg а( х)n, то элементы1Fp[x]/(a(x)) -классы многочленов степени < n(их всего•pn элементов) .Минимальный многочлен элемента(3расширенного поля есть нормированный многочлен минимальной степени, для которогоf3является корнем. Минимальные многочлены неприводимы иединственны для каждого•ЛIQбой элемент поляnмногочлена хР(3.F ==1r;является корнемх:nхР-хП (х-а).aEF•Для того, чтобы векторное подпространствокольцаR == IFР [х] / (xn - 1)Vбыло циклическим,необходимо и достаточно, чтобы оно было идеаломR.Многочленg(x)порождает идеалляется делителем2.7R, если он явxn - 1.Задачи с решениямиЗадача 2.1 .
Сумму ненулевых элементов поляРешение . Все элементы1r; -корни урав н енияIFр·88Глава1 ==xp- l их сумма по те ор емев иетаО'есть коэ2. Конечные поляфф ициентп рихр -2в этом уравнении), т. е . О .Задача2.2 (Теорема Вильсона). Док;азатъ) 'Что(р-1)!-р- 1дл.я прост о го р.Решение.== 2: - утверждение три виально .р > 2: Порядки всех элементов мультипликативной циклической группы п=-; == { 1, . .. , р - 1 } делят еёрпорядок т.е.
в се они являются корнями у равн е нияxp - l -1 ==О.Других корней у этого уравнения нет (многочленстепени р -1имеет не больше р-1корней) .П о теореме В иета их произведение равно свободному члену(*), т. е . -1.Ещё одно Решение.Для р== 2утверждение очевидно .При р>2обозначим=___11.л..__-..р==2 ..... (р - 2J1.••. (р- 1)vчетное число сомнажителеии заметим, что(р-1)!2. 7.(IIIпоток) Конечные поляЛ егко видеть, что2, ... 'р-2поляrр== 1:7Г89каждый из элементовимеет обратный, но это не р -==он обратен сам к себе . Поэтому РИли, что то же, (рЗадача2.3.Реш ен ие .р-1-1.Р - 1.1)!Построитъ поле из 4-х элементов .Это поле r~, оно может быть построено какфактор-кольцомногочлен изr2 [x]/ (а(х)),r 2 [х]степенигде а(х) - неприводимый2.Но такой многочлен только один: х + х + 1.2Следовательно, r~ == {О , 1, х, х + 1} и х == х2+1(черту над элементами не пишем).Табл ицы сложения и ум ножения в поле :1х1ох+ 1ххх+ 1о1х+ 1х1о1х11хх+ 1ххх+ 11х+ 1х+ 11х+11~1111х+1х+111Альтер нативная запись поля :r~Задача2.4.==2{о , 1, х, х } ' х2==х+ 1.Дох;азатъ) что если произво дпая пепулево го .многочлена пад поле.м харах;теристих;и р то;нсдествеппо равна О ) то оп приво ди.м.Глава90Решен и е.2.
Конечные поляИ меем:• производная моиома (xn )' = nxn- 1 тождественноравна О iff n-Р О <=? р n;• f'=Опоказатели степеней всех мономов==>многочленаfделятся на р;• поэтому f(x) = g(xP) = gP(x).Задача2.5. Найти2253Н ОД (х + х + х + 1, х + х + х + 1) надР ешен и е.523212 [х].Воспользуемся алгоритмом Евклида :х + х + х+ 1=2322(х + х)(х + х + х + 1) + (х + 1) ,2х + х + х + 1 = (х + 1 )(х + 1) + О .Задача 2.6.
Перечислитъ все подполя поля GF (2 30 ).Ре ш ен и е. Поле !F~ содержит подполе !F; iff k п,30поэтому подполями GF (2 ) будут поля GF (2) ,2101556),),),),GF (2GF (2GF (2GF (2GF (2 ) и самополе GF (2 30 ).Задача 2.7. Многочленf( x)= х532+ х + х + 1 Е !F2 [х]разложитъ на неприводимые множители .Ре ш ен и е.В поле!F2имеем х- 1 =1. f(1) = О ==> 1 -корень f.х+ 1.2. 7.(IIIпоток) Конечные поля912. Делим f(x) на х + 1, получаем4х + х + х + 1 == !1(х) .3. .!1(1) == О4. .!2(1) == О::::?::::?x1l1 - корень .!1;3== х + 1 == f2( x) .21 - корень !2; x~l == х + х + 1.5.
Многочлен хЗадача32+х+1неприводим .322.8. Мrногочлеrн f( x) == х + 2х + 4х+ 1 Е lF 5 [x]разл ожитъ rна неприводимые мrножители.Реш ение.1. f(2) == 23 + 2. 22 + 4 . 22 + 1 == 25(х-2.32х3+ 3х 22)-5 (хх + 2х + 4х + 124х24х5 о,+ 3)х+ 31-х--тт--+_4_х_+_2+ 4х+ 2х+12х + 12хо3. Перебором убеждаемся , что многочлен х 2 +4х+ 2неприводим вr 5.92ГлаваЗада ча 2.9. Многочлен2. Конечные поля4f(x) == х + х 3 + х + 2 Е IF з [х]разложить на неприводuм/ые мнoafCumeлu.Реш ен и е.1.
О , 1, 2- не корни f( x)f( x)==?линейных делителей не содержит.Н еприводимые многочлены над IFз степени2.х2х22:+ 1,+ х + 2,2х + 2х + 2.3. Подбором получаем : f(x)4Ответ: х + х + х + 2Зада ча2. 10.3==222(х + 1 )(х + х + 2) .2== (х + 1) (х +х + 2).Многочлен432f( x) == х + 3х + 2х +х+4Е !Fs[x]разлоаfсuтъ на неприводимые мноаfсuтели.Ре ш е ни е.f (х)1.т. е .2.надО ни при каком хf( x) =/=0,1 , 2,3, 4,не имеет линейных делителей.Перебир ая неприводимые многочлены степениIF 5 ,получаемОтвет:f (х) == (х22+ х + 1) (х + 2х + 4) .22. 7.(IIIпоток) Конечные поля93Зада ча 2.11 .
Разложитъ 'На 'Неnриводи.м/ые .М'НОD+еителивсе 'Нор.мирова'Н'Н'Ые .м'Ного'Чле'Н'Ы3-uстеnе'Ни изrr2 [x].Решение .х =О,Вычисляязначениямногочленовприприходим к выводу, что1,!1 (х)! 2(х)fз(х)j 4(x)f 5 (x)f 6 (x)f 7(x)====3х = х · х · х,х3х3х3х3fв(х) = х3=+ 1) (х + х + 1),22х=(х+ х = х(х + 1) ,3х + х = х (х + 1),3=+1=22+ х + 1 - неприводим,+ х + 1 - неприводим,+ х + х = х(х + х + 1),3+ х + х + 1 = (х + 1) .2222Зада ча 2.12 . Найти все 'Нор.мирова'Н'Н'Ые 'Неnриводи.мъtе.м'Ного'Чле'Н'Ьt2-uстеnе'Ни 'НадG F (3) .Решение .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
