С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 4
Текст из файла (страница 4)
Идеалa n хn+ . . . + а 1х + ао(а(х))Е [Гр [х] , a nпорождает=1О.фактор-кольцоlrp[x]j(a(x)), элементы которого суть совокупности r(x) многочленов, датощих при делении наа(х) остаток r(x):r(x) == { f(x) Е lrp[x] f(x) == а(х) ·q(x)+r(x) }.Иногда говорят, что элементыf, g Е r(x)двоuпому двоuпому модулю-р и а( х):f(x)а(х)а(х) Еlrp[x],сравнимы поg(x) .Расширения простых полейУтве ж ениелем Галуа2.2. МножествоGFr(x).являетсяпо -(рп ).Доказа тел ьс тво.1. Кольцо многочленов2.lrp[x]евклидово,(а(х)) - максимальныйr(x)Его мощностьчислоr(x)над [ГР степени не вышеn- 1, т. е .идеал- поле.многочленоврп .DПолеn-ur(x)== GF (pn)степени простого полячение-rr;.называется расширениемlrp;альтернативное обозна2.1 . (III поток) Конечные поляПочему в обозначенииr;37не используется многочлена(х), с помощыо которого построено поле?Тео ем аЛ1-обое rк;онечное поле изоморфно rк;аrк;о.му2.2.нибудъ полю Галуаr;.Пример 2.3 (построение поля IF~).
Выберем в IF3[x]2веприводимый многочлен : пусть это будет х + 1.Тогда искомое п оле 9-элемент ное п оле естьIF~[F 3 [ х] / (хrv== { О ,2+ 1)==2, х, х + 1, х + 2, 2х, 2х + 1, 2х + 2 } .I,Можно составить таблицы сложения и ум ножения в') == - 1 -3 2...этом поле с учетом х~Н апример:х+ 1 + х + 2 == 2х,2х+ 1+ х== 1,х2х-· 2х == 1+ 1·х== х'+ 1,и т.д .Черту над элементами поля1Fp[x]j(a(x))обычно не ставят и называют их <<м ногочленами >> .Но надо помнить , что это совокупности многочленов ,дающих при делении на а(х) один и тот же остаток ...Заметим, что(х+ 1 )1==х+1,(х + 1) == 2х,2(х + 1) == 2х + 2,5(х + 1) ==х,6(х + 1) == 2х + 1,(х+ 1 )7(х + 1) ==2,(х834+ 1)==х+2,==1.Глава38Это з начит, что х2.Конечные поляпримитивный элемент поля+ 1-!F~ (ах- нет, поскольку х 4 ~ 4 -з 1).А что будет, если при построении поля вместо х 2 + 1взять другой неприводимый в!F3 [x] многочлен?2Например, 2х + х + 1?Ответ: получится поле, изоморфное построенному.Пример2.4 (вычисления в конечном поле) .
Опередить ,является ли:1)многочлен а(х) ~ х 3 + 2х + 4 Е !F 5 [x]-неприводимым?2) элемент 4х 2 + 2 - корнем а(х) в факторкольце/поле !F5 [x]/ (х 3 + 2х + 4)?Решение.1.ПереборомGF(5) ~ {0, 1, 2, 3, 4}:элементова(О) ~4, f(1) ~ 2, а(2) ~ 1, а(З) ~ 2, а(4)убеждаемся а(х)-из1веприводимый многочлен (а еслибы это был многочлен 4-й степени?) .3Следовательно, фактор-кольцо !F5 [x]/ (х + 2х + 4)является полем и в нём х 3 ~ -2х- 4 ~ 3х + 1.2222. а(4х + 1) ~ (2(2х + 2)) +2 · 2(2х + 1) + 4 ~4224266З(Зх +2х +х +1)+3х +3 ~ 4х +х +х + 1 ~222224(3х + 1) + Зх + х + х + 1 ~ х + 4х + 4 + Зх +2х + х + 1 ~ О.3Как найти примитивные элементы поля ~r;?апримитивный элемент поля-F~ ~r;, если при изменении k ~ 1, 2, ... , pn - 1 значениезначения всех элементов•аРп - l ~1·'F *.akК ак следствие :пробегает2.1 .(III поток) Конечные поля39• если k взаимно просто с pn - 1, топримитинный элемент поля F.ak -другойТак могут быть получены все примитивные элементыF : их <p(pn-1) штук ==простых с pn - 1 чисел.количество взаимноНапример, в рассмотренном 9-элементном поле IF§имеется <р(8)ных== 4 примитивных элемента, образованстепенями 1, 3, 5, 7 (взаимно просты с 8) уженайденного генератора:х + 1, (х + 1) == 2х + 1, ( х + 1) == 2х + 2,357(x+ l ) ==x+2.Я что-то не понимаю: неприводимые многочлены -этопримитинные элементы?Ведь было : для поиска и тех, и других нет эффективных алгоритмов...• Веприводимые многочлены ищут в кольце многочленов1Fp[x] над простым полем 1Fp -например,чтобы построить расширение поля.• Примитинные элементы ищут в мультипликативной группе поля-например, чтобы иметь удобное представление иенулевых элементов поля через степени п р имитивного элемента.Замечание.
В поле понятие << неприводимый многочлен >>не имеет смысла: там лiобой многочлен делится на ЛIОбой ненулевой . Например, в IF 3 [х] / (хx+ l==2х + 1х.2+ 1) :Глава 2. Конечные поля40Может ли приводимый многочлен быть примитивнымэлементом?1. Возьмём поле IF 2 = {О , 1 } .2. В озьмём неприводимый над IF 2хз + х + 1.многочленIF2[x]/ (хз + х + 1) rv IF~;оно содержит все полиномы из IF 2[х] степени ~ 2.3.
Построим поле F=24. Многочлен Ь (х) = х +х = х(х+ 1 ) - приводимв Л}обом кольце, в т.ч . - в IF 2[x], и он принадлежитF.5. Является ли Ь(х) - примитивным элементом поля F?МультипликативнаягруппаполяF2з - 1 = 7 элементов, это простое числотипликативная группе все ср( 7) =метав6содержитнеединичных элегенераторы =} ответ на оба вопроса-в муль=}-ДА !2Удостоверимся, что а = х + х = х (х + 1) - примитивный элемент поля F = IF 2 [x]/ (xз + х + 1) .В F хз = х + 1 иа =х2+ х,а2 = х4 + х2 = :/2 + х+ :/2аз =а ·а2= хз + ха4 = (а2)2 =52а64а72=Х2'= х + х + 1,х2,а = а аз = хз + х + х = :/ + 1 + х + :/ = х + 1,=2х + х + 122=22х + х+ х + 1= х (х + х + 1) = х + хз + х=22:/2+4:/+ :/+ 1+:/2=1.22х+ 1,2.1 .(III поток) Конечные поля41Всегда ли неприводимый многочлен есть примитинныйэлемент?1.2.Возьмём полеВозьмёмх2IF 5 == {0, 1, 2, 3, 4}.неприводимый над IF 5 многочлен+ х + 1.3.
Построим поле F == IF 5 [х]/ (х2+ х + 1)rvIF~;оно содержит только полиномы 0-й и 1-й степеней из4.IF 5 [х] .Все многочлены 1-й степени неприводимы, имеют+Ьвид ахВсе ли онии их-шт.- 20примитинные элементы поляF?Мультипликативная группа поля F содержит 5 21 == 24 элемента из которых <.р(24) == 8 примитивных::::} не все многочлены 1- й степени - генераторы ::::}ответ на оба вопроса - НЕТ!Удостоверимся , что а == х не есть примитивный2[элемент поля F == IF 5 х] / (х + х + 1) .В F: х2а2==-х - 1 == 4х+4и==х+ 4,==4х + 4ха ==4ха32Вопрос: когда корень1 6хх+ 16 + 4х ==1.(сам неприводимый многочлен!) неприводимого над!Fpпримитивным элементом полямногочлена а(х) будетIFР [х] / (а (х))?Ответ: это будет если и только если многочлен а(х)при.митивеп для х, т.е .показатель, при которомт== pn - 1 а( х) xm - 1.наименьшийГлава 2.
Конечные поля42Пример2.5. 1. Н еприводимый3х + х + 1 примитивен:23х -1надIF 23многочлен1 == х + 1 == ( х + х + 1) · ( х + х + х + 1)7-и xt - 1iх3+х+142ни при каком 1 :( t< 7 == т.П оэтому30IF~ [х] / ( х + х + 1) == { х == 1, х , х , х == х + 1,42152236х == х + х, х == х + х + 1, х == х + 1 }-все многочлены степени не выше22.2.
Неприводимый над IF 2 многочлен х4 + х 3 + х 2 + х +24 11 не примитивен: он делит не только бином х 151 == х - 1, но и бином х 5 - 1:х551 == х + 1 == ( х + х + х + х + 1) · (х + 1),-или , что тоже ,5443ord х == 53i=215:2х == (х +х +х +х+ 1 ) · (х+ 1 )+ 11.=02.2Вычисление в конечных поляхАлгоритм Евклидаприменяют для нахожденияНОД(а, Ь) натуральных чисел а и Ь.Наблюдение: общий делитель пары чисел (а, Ь), то остаётся им и для пары (а- Ь , Ь) (считаем, что а~ Ь).Отсюда:• пары чисел (а, Ь) и (а - kb, Ь) имеет одинаковыеобщие делители;(III поток) Конечные поля2.2.43• вместо а - kb (для <<ускорения>>) можно взятьостаток r 0 от деления нацело а на Ь : а == bq +ro, q Е IN, О ~ ro < Ь;•затем,переставивчиславп ар е,можноповтор ить процеду р у; она закончится , т.к.
числа в пар еуменьшаются , но остаются неот р ицательными .В результате: за конечное число шагов обр азуется пар а(rп, О) и ясно , что НОД(а, Ь)== rп ( НОД -англ . gcd) .Алгоритм Евклида: общая схема (а ~ Ь)Ш аг( -2): r -2а-полагаем для удобства;Ш аг(-1): r - 1Ь-полагаем для удобства;Ш аг0:== r_l qo + ro -r-21: r - l == roql +r1- делим r - lШ агr_l ,ro;остаток.. .делим r-2 нанаro,остаток r 1;всегда делим с остатком большее число на меньшее,наследующемшагемень шеестановится большим, а остатокШ агn : rп-2 == rп-lqn+ rп--n+ 1:делим rп-2 на rп-l ,Tn- lОСТАНОВ.НОД(а,Ь)Всегдаr-2~==ономеньшим;остаток rп;Ш агчислоrпr_l > ro > r1 > ...
> r n~1.(III поток) Конечные поля2.2.45Расширенный алгоритм Евклидадвум натуральным числамаиЬнаходит поих натуральныйНОДd и два целых х, у коэффициента Везу (таких,чтох1Ь d, у<<1а d ).Р асширенный алгоритм Евклида повторяет схему(простого) алгоритма Евклида, в котором на каждомшаге :1) дополнительно вычисляются Xi и Yi по формуламXi=Xi- 2 -Х-2qiXi-l, Yi== Y- l =1 ' X- l=qiYi- l , iYi-2 -=У-2=оо,1, ..
.;;2) справедливо соотношениеri =r i- 2 -+ byi- 2) - qi (axi-l + byi-1)a(xi-2- qixi- l ) + b(Yi-2 - qiYi- 1) = axi + byi .==При мерqiri- l =2.7.Р асширенным алгоритмом Евклида найдёмнатуральноеdИмеем( axi-2=Xiи целые х и у такие, чтоdН ОД=(252, 105)Xi-2 -=qiXi-l, Yi252х=+ 105у .Yi -2 -qiYi-l ·Сведём все вычисления в таблицу :шаг•~-2- 1о12ri-2ri-lqiriXiYi252 1 о105 о1252 105 2 42 1 -2105 42 2 21 -2 542 21 2 оГлава46Ответ:d == 21,2.Конечные поля== - 2, у== 5, т. е .21 == 252 . (-2) + 105 . 5.хПример 2.8. В полеZ/(101) решить уравнение4х==( *)1.Р е ш ен и е.1.4хх== 1 + k · 101 == 102, 203, 304== 304/4 == 76.Это решение перебором .2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
