PA_full (1127144), страница 7
Текст из файла (страница 7)
+ apk xkp == a0 + a1 (xp ) + a2 (xp )2 + . . . + ak (xp )k ,т.е. для любого многочлена f (x) 2f (x)Отсюда:и ,p,pp [x]выполняется равенство= f (xp ).'( ) = 0 , '( )p = 0 , '(...,pn1� корни многочлена '(x).(⇤)p)=0Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем73 / 432Многочлены над конечным полем...n 1(2) Осталось доказать, что все , p , . . . , pразличны, итогда (поскольку многочлен степени n имеет не более n корней)можно утверждать, что найдены все корни многочлена '(x).lkПредположим, что p = p и без ограничения общностиl < k.
Имеем:12pn= ;посколькуpnто=pk ·pnk=⇣pk⌘p n� корень уравнения xk=pn k+l1⇣pl⌘p nk=pnk+l,1 = 0.Из теоремы �Все неприводимые многочлены n-й степени надpnx� получаемp являются делителями xn k + l > n ) l > k � противоречие.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над 2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении 42 .74 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над 2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении 42 .Один корень получаем немедленно: x.74 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над 2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении 42 .Один корень получаем немедленно: x.По только что доказанной теореме можно выписать остальные:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x .74 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем74 / 432Многочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над 2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении 42 .Один корень получаем немедленно: x.По только что доказанной теореме можно выписать остальные:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x .Покажем, что, например, x2 действительно корень f (x):x4 + x3 + 1x 7! x22= x4·2 + x4+2 + 1x4 7! x3 +16== (x3 + 1) + (x3 + 1)x2 + 1 = x + 6 1 + x5 + x2 + 6 1 == x6 + x5 + x2 = x2 (x4 + x3 + 1) = x2 · 0 = 0.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + .
. . + an xn = 0,a 0 , a1 , . . . , a n 2p.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + . . . + an xn = 0,a 0 , a1 , . .
. , a n 2p.Если f (x) �неприводимый многочлен, то строим полекотором корнями f (x) будутx, xp , . . . , xpn 1 ;p [x]/(f ),вПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + . . . + an xn = 0,a 0 , a1 , . . . , a n 2p.Если f (x) �неприводимый многочлен, то строим полекотором корнями f (x) будутx, xp , . . .
, xpn 1 ;p [x]/(f ),вимеет делители, то раскладываем f (x) на неприводимыемножители и находим их корни как в п. 1), полученныекорни объединяем.Одновременно строится минимальное поле характеристикиp, в котором данный многочлен f (x) раскладывается налинейные множители.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + .
. . + an xn = 0,a 0 , a1 , . . . , a n 2p.Если f (x) �неприводимый многочлен, то строим полекотором корнями f (x) будутx, xp , . . . , xpn 1 ;p [x]/(f ),вимеет делители, то раскладываем f (x) на неприводимыемножители и находим их корни как в п. 1), полученныекорни объединяем.Одновременно строится минимальное поле характеристикиp, в котором данный многочлен f (x) раскладывается налинейные множители.В конце данного раздела будет дан алгоритм нахождения всехкорней многочлена f (x) над полем Галуа p для общего случая.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования. Коды ХэммингаГрупповые (линейные) коды76 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств77 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать78 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа расширения поляПример (поле4)2Поле 42 можно строить с помощью любого из трехнеприводимых многочленов (но пока не доказано):x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Удобнее всего это сделать, если взять многочленf (x) = x4 + x + 1 (почему?).79 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа расширения поляПример (поле4)2Поле 42 можно строить с помощью любого из трехнеприводимых многочленов (но пока не доказано):x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Удобнее всего это сделать, если взять многочленf (x) = x4 + x + 1 (почему?).Будем задавать элементы 42 наборами коэффициентовмногочлена-остатка при делении на f , записывая их в порядкевозрастания степеней.Порождающим является элемент ↵ = x, который записываетсякак (0, 1, 0, 0).Вычислим степени ↵, сведя результаты в таблицу.79 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа поля↵4 = ↵ + 14280 / 432⇠=степень ↵↵=↵2 =↵3 =1 + ↵ = ↵4 =↵ + ↵2 = ↵5 =↵2 + ↵3 = ↵6 =3↵ + ↵ + 1 = ↵3 + ↵4 = ↵7 =1 + ↵2 = ↵ + 1 + ↵2 + ↵ = ↵8 =↵ + ↵3 = ↵9 =22↵ + 1 + ↵ = ↵ + ↵4 = ↵10 =↵ + ↵2 + ↵3 = ↵11 =231 + ↵ + ↵ + ↵ = ↵2 + ↵3 + ↵4 = ↵12 =1 + ↵2 + ↵3 = ↵ + ↵2 + ↵3 + ↵4 = ↵13 =1 + ↵3 = ↵ + ↵3 + ↵4 = ↵14 =1 = ↵ + ↵4 = ↵15 =2 [x]/(x1(0,(0,(0,(1,(0,(0,(1,(1,(0,(1,(0,(1,(1,(1,(1,4x1,0,0,1,1,01,0,1,1,1,1,0,0,0,+ x + 1)x20,1,0,0,1,1,01,0,1,1,1,1,0,0,x30)0)1)0)0)1)1)0)1)0)1)1)1)1)0)Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов81 / 432Имея такую таблицу, очень просто производить умножение(x3 + x + 1) · (x2 + x + 1) = ?Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов81 / 432Имея такую таблицу, очень просто производить умножение(x3 + x + 1) · (x2 + x + 1) = ?1перемножить, учитывая x4 = x + 1 � можно, но сложно...Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов81 / 432Имея такую таблицу, очень просто производить умножение(x3 + x + 1) · (x2 + x + 1) = ?1перемножить, учитывая x4 = x + 1 � можно, но сложно...2с помощью таблицы:представляем многочлены в векторной форме и по ней � ввиде степеней ↵ = x:x3 + x + 1 $ (1, 1, 0, 1) $ ↵7 ,x2 + x + 1 $ (1, 1, 1, 0) $ ↵10перемножаем, получаем: ↵7 ↵10 = ↵17 = ↵2 = x2 .Получаем: (x3 + x + 1) · (x2 + x + 1) = x2 .Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m � максимальный порядок элемента в конечнойабелевой группе G.Тогда порядок любого элемента x 2 G = h G, , e i делит m.82 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m � максимальный порядок элемента в конечнойабелевой группе G.Тогда порядок любого элемента x 2 G = h G, , e i делит m.ДоказательствоГруппа G однозначно разлагается в прямую сумму циклическихгрупп, порядки которых являются степенями простых чисел.Для каждого простого делителя pi порядка группы найдемциклическую группу максимального порядка pki .Обозначим произведение чисел pki через M .
Для любогоx 2 G выполняется xM = e, т.е. порядок x делит M .Но произведение всех выбранных циклических групп имеетпорядок M . Поэтому m = M .82 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля q размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над p .(везде p � простое, n � натуральное).83 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля q размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над p .(везде p � простое, n � натуральное).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
