С.И. Гуров, Д.А. Кропотов - Конспект лекций по курсу Прикладная алгебра (1127136), страница 5
Текст из файла (страница 5)
Поскольку 1 0 1у101 О , вместо( *) можно расширенным алгоритмом Евклида решать уравнение4х+ 101 у ==1.В результате работы алгоритма получим:4 . 76 + 101. (-3) == 1.Аналогично решаются уравненияах==сиах+ Ьу ==с(а, Ь и с надо поделить на их общий Н ОД).Алгоритм Евклида и его расширенная версия остаются справедливыми в л1обом евклидавам кольце, следовательно, и в любом поле Галуа .Поэтому обратный элемент у(х) элемента Ь(х)вполе 1Fp[x]j(a(x) ) , определяемый соотношениема(х)'· х(х)v+Ь(х)· у(х) == 1,.1=0для пары многочленов (а( х), Ь( х) ) , может быть найденрасширенным алгоритмом Евклида.2.2.(IIIпоток) Конечные поляРешениегда:т. к .данныха(х)47соотношенийсуществуетвеприводимыйdeg Ь(х) < deg а(х) , то НОД (а(х), Ь(х))все-многочлени== 1.+ х + 3) - 1 в поле4IF7[x]j (x + х + х + 3).Пример 2.9.
Найдём (х232Для этого расширенным алгоритмом Евклида реIп им соотношение(х4322+ х + х + 3) . х (х) + (х + х + 3) . у(х) ==Ш аг 0: r_2(x) == х + х + х + 3,r_l(x) == х + х + 3,431. (*)22У-2(х)Y- l (х)== О ,== 1- заданиеначальных значений .Ш аг 1:r-2(x) == r_l(x)qo(x) + ro(x),2qo(x) == х + 5,ro (x) == 2х + 2,Уо(х) == У-2(х) - Y-l (х )qo(x) == - qo (x) ====Ш аг 2:r - l ( х) == r о (х) Ql (х)Q1 (х)r 1 ( х)Yl (х)2-х - 5.+ r 1 ( х) ,== 4х,== 3, deg r 1 ( х) == О== у - l ( х) - Уо (х ) Q1 ( х) ==23== 1 + 4х (х + 5) == 4х + 6х + 1.Алгоритм заканчивает свою работу на шагеdeg r 1 ( х)== deg 1 ==2,т.к.О( 1 - многочлен в правой части ( *) ) .Замечание: при итерациях алгоритма нет необходимости вычислятьXi (х), т.к .
нас интересует только значения Yi (х) , i == О, 1, ... .Глава 2. Конечные поля48Остатокr 1 ( х) == 3, отличается от 1 на множительконстанту. Чтобы получить решение уравнения (*) вы1числяем элемент 37 5 и домножаем на него У1 :35у 1 ( х) == 5 (4х + 6х + 1)4Ответ: в поле IF 7 [х]/ (х + х + х +2372136х + 2х + 5.3)имеем(х + х + з) - == 6х + 2х + 5.Алгебра2.33векторовнадконечнымполемВекторное пространствоОпределение 2.1 . Абстраrк;тны.м веrк;торнъt.м пространство.м над полем [k == {1, а, j3, ... } называется двухосновная алгебраическая система V == ( V, [k; +, · ) ,где• V== {О ,v, .
. . } -произвольное множество веrк;торов ,+ - бинарная операция сложения над•V:v х v ~ v,бинарная• · -операцияумножения(<< числа>> ) из [k на вектор из••причем операции+и·V:[k хVэлемента~V,удовлетворяют следующим ак-с ио мам :1) V - коммутативная группа по сложению + , О ..uuее н еит ральны м элемент;2.3.(IIIпоток) Конечные поля492) a ·(v1+v2) == a ·v1+a ·v2, (a1+a2) ·v3) а · ((3 · v) == (af3) · v ;4) 1 ·v==v .Пр имер2.
10.ПустьV ==множество конечных по[kn -следовательностей длиныnэлементов поля0<.'Сложение' и 'умножение на число из [k' элементов изVопределяются покомпонентно .П олучившаяся структураство,егоназывают-п-.мер 'Н/Ьl.Мвекторное пространгх;оордипатпъt.мпрострапство.м над полем [k .Дистрибутивность относительно вычитания(а - (3) · v(а -== a · v - f3 · v:+ (3 · v(3) · v== (а - (3 + (3) · v == а · vОтсюда получаем, чтоО•· v ==• и -vО , так как О== (- 1) · v,· v == (1 - 1) · v == v - v ==так какv+( -1 )·v == 1 ·v+( -1) · v == (1-1)·v == O· vУтве ж ение2.4.Поле харагх;теристигх;и рвегх;торное пространство надДоказа тельство.ВО,G F (р)(ррассматриваемом->О== О.естъпростое).полеGF (q),q ?::- р:сложениеумножениенаследуется операция сложения вGF(q);- п осколькуGF (р) == { О , I, ...
, р - 1 } с G F (q) ,то при умножении <<чисел>> из поля GF(p) на векторы из GF(q) можно заменять на умножениеэлементовGF(q);Глава 2. Конечные поля50аксиомы векторного пространства-выполняFотсявсилу свойств арифметических операций в полеGF(q) .DСле ствие . Лоле Гал уахарак;теристик;и р к; ах;G F (q)век;тор?-lое простра?-lство состоит изpnэле.ме?-lтов:q == pn.Представление элементов конечных полей.1r;ле== {с элементамиЬоM p,n (х)+ Ь1х + ... + Ьn- lXn-11П о-==Ьо , Ь1 , ...
, Ьn-l Е 1Fp } ,можно рассматривать как1)фактор-кольцо 1Fp[x]j (a( x) ) вычетов 1Fp [x] поидеалу векото ро го веприводимого м ногоч ленаа(х) == ао+ а1х + ... + anxn,ао, а1 , .. . ,anЕ1Fpили как2)п-мерное координатное пространство над IFP:\ M p,n(x), 1Fp;(все операции-поmod+, ·)р ) и в обоих случаях можноопределить операЦИI{) деления на иенулевой элемент.2.3.-1 -'х,...'хn-1.Базисобразуютэле.ме'Нты2.3.(IIIпоток) Конечные поляДоказа тельство.1.51ЛIQбой элемент п=-; представим ввиде линейной комбинации указанных векторов :Ьо+ Ь1 х + ... + Ьn- l xn- l2.=== Ьо 1+ Ь1 х + ... + bn- lxn- lПустьс(х)о.Это означает, что многочлен с( х) степенися н а некоторый м ногочленп-й степени , что возмож-но лишь при со === с1 === .•• ===1' -х , . . .
' х n-ln - 1 делитCn- l=== О , т.е. системалинейно независима.DЗамечание. Построение поля с помощыQ вычетов по модулю в екоторо го в еприводимого многочлена и аналогидо казанных тео р ем справедливы не только в случае конечных полей.Например :1) рассмотрим поле действительных чисел [R и кольцо многочленов [R [х] над ним;2) в lR[x] возьмём веприводимый многочлен х3) построимполе2F === [R [х] / (х + 1);Fкак2+ 1;фактор-кольцо:4) F также и векторное пространство над lR; его базис- { 1, х } и каждый его элемент z Е F можно представить в виде z === а1 + Ьх, а, Ь Е lR;5) поле F изоморфно полiо комплексных чиселС === { а + i b а , Ь Е [R, i === - 1 } ,2изомо рфизм задаётся соответствием1 н.
1,хн.i.52Глава~ 2.2. Поле1r;Доказа тельство .Если2.Конечные полясодержит подполеполеlk 11r;iff k n .содержитсявполе( lk 1 С lk2), то элементы lk2 можно умножать на элементы из lk 1 , а результаты складывать.П оэтому поле lk2 является векторным пространством над полем lk 1 некоторой размерности d- значит,..lkdв немэлементов.1Наш случай: pn === (pk)d, что и означает k1n.Обратное следует из существования и единственно-сти (с точностью до изоморфизма) полей Галуа.Ясно , что IFР -всегда подполе1r;(случайkо===1).Наиболее употребимы два представления элементов кон ечного полявекторноеве кторстепенноеF === IF;:-каждый элементб а з исев-F записывается-1, х 1 , х 2 , ...
, хn - 1 ;каждый иенулевой элементFкакзаписывается как некоторая степень генератора мультипликативной группыF*.Кстати, что такое хВ поле•1r;?=== IFр[х]/ ( а(х))х есть совокупность всех многочленов из IFР [ х] ,дающих при делении на а(х) остаток х;• х===(0, 1, О, . . . , О)Е (!Fр)п.В дальнейшем, как принято, вместо х обычно пишемп ростох.(III поток) Конечные поля2.4.53Замечание. П ер еход от степенного представления к векторному достаточно прост, а обратный переход-оченьсложен, т. к . связан с вычислением дuск;ретного логарифма (н атуральногоzв равенствеa z :=:ь).На сложности этой задачи (известны не более , чемсубэкспоненциальные алгоритмы её решения) базируются методы криптогр афии с отрытым клiочом .2.4Корни многочленов над конечнымполемМинимальныйf3многочлен .Р ассмотримэлементконечного поля и будем интересоваться м ногочленами, для которых он яв ляется корнем.Определение 2.2.
Минималънъtм многочленом (м. м.)элементаf3Ечлен тJЗ(х) Еf3G F (pn) называется приведённый много1Fp[x] наименьшей степени , для которогоявляется корнем.Докажем далее, что м.м. для каждого элемента(3:1) существует,2) единственен,3) неприводим .Сразу заметим , что минимальный многочлен можно получить из неприводимого .Рассмотрим поле F1Fp[x]f(a(x)) , порождаемоев е прив одимым многочленома(х) === ао+ а1х + ... + anxnГлава54и убедимся, что многочленan1а(х)== ( О , 1, О , ... , О )для элемента х2. Конечные поляЕ-минимальныйF.Я сно, чтох2== х 2 == (0, 0, 1, 0, .
. . , 0),Далее , с одной стороныао+ а 1х + . . . + an(х) n ==а значит и. . . , xn- 1 == (0, . . . , 0, 1)х - корень а( х), т. к.ао+ а1 х + . . . + anxn ==-О,1an а(х).С другой-если ::J Ь(х)==Ьо+ Ь1х + .. . + Ьп- 1 (х )n- l == О,то Ьо 1 + Ь1х + ... + Ьn-l xn- ==1т. е .и меем'-'линеинуюI , х, ... , xn- 1==Ь1== ... ==Ьп- 1междубазиса поляго пространства надЬозависим ость==FО,элементамикак векторно-что возможно только при1Fp,О.Примитинные многочленыПри мер2.11 .31.
Многочлен а(х) == х + х + 1 неприводим в IF 2 [х],следовательно F == IF 2 [x]j(a(x)) -поле и по доказанному ранее а(х)- минимальный многочленДЛЯ Х.Пр имитивен ли этот элемент х ЕF *?Проверяем, что в F == GF(2 3 ) a(x)J(xt - 1) при7t == 3, 4, 5, 6 (а делимость х - 1 на а(х) всегдабудет иметь место : хх+ 1) ).7+ 1 ==(х3+ х + 1)(х + х +422.4.(III поток) Конечные поля55Это означает, что хF 9- примитивный элементF * 9 ord х == 7.генераторполя2. Многочлен а(х) == х 4 + х 3 + х 2 + х + 1 неприводим в lr2[x], следовательно F == lr2[x]j(a(x))поле и по доказанному ранее а(х) - минимальный многочлен для х .Примитивен ли элемент х?Имеем в F5а(х)== GF(254):432(х - 1 ) : х + 1 == (х +х +х +х+ 1 )(х+ 1 ) .3Или: F* == 15 == 3 · 5, х # 1, но2543х == х · х == х · ( х + х + х + 1) == 1.Это означает, что х - не есть примитивный многочлен и х-не генератор F *, т.
к. ord х == 5 # 15.Определение 2.3 (эквивалентное данному ранее). Минимальный многочлен примитивного элемента поля называется при.митивны.м .многочленом.Свойства минимальных многочленов~~~""'е"V"н~и""""е2.5. Ми 'Н и.мал ъ 'Н ые .м 'Н о г о чл е 'Н ы 'Н е nр и в о-ди.мъt.Доказательство. Пусть mrз (x)- м.м. степени т дляи mrз (x) ==f3m1(x) · m2(x).Тогдано степенипоэтомуf3m1(f3) ==Оmrз ((3) == о ==>m2(f3) == О 'многочленов m 1(x) и m2(x) меньше m,ине может быть их корнем .оГлава562. Конечные полянеприводимые(н ера зло ж и м ь1 е)минимальныепримитивные(минимальнь1е дляnримити вных элементов)Р ис.2.1.Соотношение множеств неп риводимых , минимальных и примитивных многочленовУтве ж ениеmrз (х)-2.6 .Пустъвпек;оторо.м.м .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
