PA_full (1127144), страница 3
Текст из файла (страница 3)
Почему?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа25 / 432Построение конечных полей� с использованием неприводимых многочленов.1234Выбираем простое⌦ p и фиксируем поле↵={ 0̄, 1̄, . . . , p 1}, +mod p , ·mod p .pОбразуем кольцоp [x]многочленов над ним.Выбираем натуральное n и неприводимый многочленP (x) = an xn + .
. . + a1 x + a0 2 p [x].Идеал (P (x)) порождает фактормножество p [x]/(P (x)),элементы которого суть совокупность {R(x)} остатков отделения многочленов f 2 p [x] на P (x):f (x) = Q(x) · P (x) + R(x) .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа25 / 432Построение конечных полей� с использованием неприводимых многочленов.1234Выбираем простое⌦ p и фиксируем поле↵={ 0̄, 1̄, . . .
, p 1}, +mod p , ·mod p .pОбразуем кольцоp [x]многочленов над ним.Выбираем натуральное n и неприводимый многочленP (x) = an xn + . . . + a1 x + a0 2 p [x].Идеал (P (x)) порождает фактормножество p [x]/(P (x)),элементы которого суть совокупность {R(x)} остатков отделения многочленов f 2 p [x] на P (x):f (x) = Q(x) · P (x) + R(x) .УтверждениеМножество {R(x)} является полем Галуа GF (pn ).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение конечных полей...Доказательство12кольцо многочленов p [x] евклидово, идеал (P (x)) �максимальный ) {R(x)} � поле;{R(x)} = число многочленов над p степени не вышеn 1, т.е. {R(x)} = pn .26 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа26 / 432Построение конечных полей...Доказательство12кольцо многочленов p [x] евклидово, идеал (P (x)) �максимальный ) {R(x)} � поле;{R(x)} = число многочленов над p степени не вышеn 1, т.е.
{R(x)} = pn .Поле Галуа {R(x)} называетсярасширением n-й степени поляpи обозначаетсяn.pВопросПочему в обозначении np не используется многочлен P (x), спомощью которого построено поле?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа26 / 432Построение конечных полей...Доказательство12кольцо многочленов p [x] евклидово, идеал (P (x)) �максимальный ) {R(x)} � поле;{R(x)} = число многочленов над p степени не вышеn 1, т.е.
{R(x)} = pn .Поле Галуа {R(x)} называетсярасширением n-й степени поляpи обозначаетсяn.pВопросПочему в обозначении np не используется многочлен P (x), спомощью которого построено поле?ТеоремаЛюбое конечное поле изоморфно какому-нибудь полю Галуаn.pПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПример: построение поля27 / 43223Выберем неприводимый многочлен вИскомое поле есть23⇠=3 [x]/(x=23 [x] :x2 + 1.+ 1) =0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2Можно составить таблицу сложения и умножения в этом поле сучётом x2 = 1 ⌘3 2.Например:(x + 1) + (x + 2) = 2x,(2x + 1) + (x) = 1,и т.д.(x) · (2x) = 1,(2x + 1) · (x) = x + 1,Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 4322 ...3Заметим, что, например,(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 4322 ...3Заметим, что, например,(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Это значит, что x + 1 � примитивный элемент (генератор)мультипликативной группы поля 23 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 4322 ...3Заметим, что, например,(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Это значит, что x + 1 � примитивный элемент (генератор)мультипликативной группы поля 23 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в 3 [x] многочлен?Например, 2x2 + x + 1?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 4322 ...3Заметим, что, например,(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Это значит, что x + 1 � примитивный элемент (генератор)мультипликативной группы поля 23 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в 3 [x] многочлен?Например, 2x2 + x + 1?Ответ: получится поле, изоморфное построенному.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа29 / 432Число неприводимых многочленов в полеnpНеприводимый многочлен f (x) � в поле np � примитивныйэлемент мультипликативной группы Fpn⇤ , т.е.12f (x)pn 1= 1 и f (x)i6= 1 для 0 < i < pnдля любого многочлена g(x) 2in⇤p1,найдётся степень iтакая, что g(x) = f (x) , i 2 { 0, 1, .
. . , pn1 }.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа29 / 432Число неприводимых многочленов в полеnpНеприводимый многочлен f (x) � в поле np � примитивныйэлемент мультипликативной группы Fpn⇤ , т.е.12f (x)pn 1= 1 и f (x)i6= 1 для 0 < i < pnдля любого многочлена g(x) 2in⇤p1,найдётся степень iтакая, что g(x) = f (x) , i 2 { 0, 1, . . . , pn1 }.Если ↵ � примитивный элемент поля GF (q), то любой другойпримитивный элемент может быть получен как степень ↵k , гдеk � целое число взаимно простое с q 1 ) количестворазличных примитивных элементов в поле np равно '(pn 1).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа29 / 432Число неприводимых многочленов в полеnpНеприводимый многочлен f (x) � в поле np � примитивныйэлемент мультипликативной группы Fpn⇤ , т.е.12f (x)pn 1= 1 и f (x)i6= 1 для 0 < i < pnдля любого многочлена g(x) 2in⇤p1,найдётся степень iтакая, что g(x) = f (x) , i 2 { 0, 1, .
. . , pn1 }.Если ↵ � примитивный элемент поля GF (q), то любой другойпримитивный элемент может быть получен как степень ↵k , гдеk � целое число взаимно простое с q 1 ) количестворазличных примитивных элементов в поле np равно '(pn 1).Например, в поле62из 64 элементов'(63) = '(32 · 7) = 31 · 2 · 6 = 36примитивных элементов = неприводимых многочленов.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды30 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств31 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать32 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)� он понадобится для вычислений в конечных полях.Наблюдение: если d � общий делитель пары чисел (a, b), то dостаётся общим делителем для чисел (a b, b).Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)� он понадобится для вычислений в конечных полях.Наблюдение: если d � общий делитель пары чисел (a, b), то dостаётся общим делителем для чисел (a b, b).Отсюда:пары чисел (a, b) и (aобщие делители;kb, b) (k 2 ) имеет одинаковыеПрикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)� он понадобится для вычислений в конечных полях.Наблюдение: если d � общий делитель пары чисел (a, b), то dостаётся общим делителем для чисел (a b, b).Отсюда:пары чисел (a, b) и (aобщие делители;kb, b) (k 2 ) имеет одинаковыевместо a kb можно взять остаток r0 от деления нацело aна b: a = bq + r0 , q 2 , 0 6 r0 < b;Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)� он понадобится для вычислений в конечных полях.Наблюдение: если d � общий делитель пары чисел (a, b), то dостаётся общим делителем для чисел (a b, b).Отсюда:пары чисел (a, b) и (aобщие делители;kb, b) (k 2 ) имеет одинаковыевместо a kb можно взять остаток r0 от деления нацело aна b: a = bq + r0 , q 2 , 0 6 r0 < b;затем, переставив числа в паре, можно повторитьпроцедуру; она закончится, т.к.
числа в паре уменьшаются,но остаются неотрицательными.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)� он понадобится для вычислений в конечных полях.Наблюдение: если d � общий делитель пары чисел (a, b), то dостаётся общим делителем для чисел (a b, b).Отсюда:пары чисел (a, b) и (aобщие делители;kb, b) (k 2 ) имеет одинаковыевместо a kb можно взять остаток r0 от деления нацело aна b: a = bq + r0 , q 2 , 0 6 r0 < b;затем, переставив числа в паре, можно повторитьпроцедуру; она закончится, т.к.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
