AA3-1(GF-I) (1127138), страница 3
Текст из файла (страница 3)
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа18 / 71Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fpсуществует— докажем позже.ВопросКак в кольцеFp [x]найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы «Алгебры» Ван дерВардена, алгоритм Берлекэмпа...)Если многочлен не имеет корней, это ещё не значит, что оннеприводим. Почему?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаЗачем нужны неприводимые многочлены?19 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаЗачем нужны неприводимые многочлены?Используя неприводимые многочлены, можно строить новыеконечные поля — расширения простых полей Fp19 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаЗачем нужны неприводимые многочлены?Используя неприводимые многочлены, можно строить новыеконечные поля — расширения простых полей Fp :1Выбираем простое p и фиксируем полеFp = { 0̄, 1̄, .
. . , p − 1}, +p , ·p .2Рассматриваем кольцо3Выбираем натуральное n и неприводимый многочленP (x) = an xn + . . . + a1 x + a0 ∈ Fp [x].4Fp [x]многочленов над ним.Идеал (P (x)) порождает фактормножество Fp [x]/(P (x)),элементы которого суть совокупность {R(x)} остатков отделения многочленов f ∈ Fp [x] на P (x):f (x) = Q(x) · P (x)+R(x) .УтверждениеМножество {R(x)} является полем Галуа GF (pn ).19 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПостроение конечных полей...Доказательство12Кольцо многочленов Fp [x] евклидово, идеал (P (x)) —максимальный ⇒ {R(x)} — поле.Его мощность {R(x)} = числомногочленовнад Fpстепени не выше n − 1, т.е. {R(x)} = pn .20 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПостроение конечных полей...Доказательство12Кольцо многочленов Fp [x] евклидово, идеал (P (x)) —максимальный ⇒ {R(x)} — поле.Его мощность {R(x)} = числомногочленовнад Fpстепени не выше n − 1, т.е.
{R(x)} = pn .Поле {R(x)} = GF (pn ) называется расширением n-й степениполя Fp ; альтернативное обозначение — Fnp .ВопросПочему в обозначении Fnp не используется многочлен P (x), спомощью которого построено поле?20 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа20 / 71Построение конечных полей...Доказательство12Кольцо многочленов Fp [x] евклидово, идеал (P (x)) —максимальный ⇒ {R(x)} — поле.Его мощность {R(x)} = числомногочленовнад Fpстепени не выше n − 1, т.е. {R(x)} = pn .Поле {R(x)} = GF (pn ) называется расширением n-й степениполя Fp ; альтернативное обозначение — Fnp .ВопросПочему в обозначении Fnp не используется многочлен P (x), спомощью которого построено поле?ТеоремаЛюбое конечное поле изоморфно какому-нибудь полю ГалуаFnp .ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПример: построение поля21 / 71F23Выберем неприводимый многочлен вИскомое поле естьF23 ∼= F3 [x]/ x2 + 1 =F3 [x] :x2 + 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,ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПостроение поляF23 ...Заметим, что, например,(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.22 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПостроение поляF23 ...Заметим, что, например,(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 — примитивный элемент(мультипликативной группы) поля F23 .22 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаПостроение поляF23 ...Заметим, что, например,(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 — примитивный элемент(мультипликативной группы) поля F23 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в F3 [x] многочлен?Например, 2x2 + x + 1?22 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПостроение поляF23 ...Заметим, что, например,(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 — примитивный элемент(мультипликативной группы) поля F23 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в F3 [x] многочлен?Например, 2x2 + x + 1?Ответ: получится поле, изоморфное построенному.22 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаКак найти примитивные элементы поля23 / 71Fnp ?f (x) — примитивный элемент (генератор) группы Fn∗p , еслиipn −11= 1 и f (x) 6= 1 для 0 < i < pn − 1,f (x)2для любого многочлена g(x) ∈ Fn∗p найдётся степень iiтакая, что g(x) = f (x) , i ∈ { 0, 1, .
. . , pn − 1 }.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКак найти примитивные элементы поля23 / 71Fnp ?f (x) — примитивный элемент (генератор) группы Fn∗p , еслиipn −11= 1 и f (x) 6= 1 для 0 < i < pn − 1,f (x)2для любого многочлена g(x) ∈ Fn∗p найдётся степень iiтакая, что g(x) = f (x) , i ∈ { 0, 1, .
. . , pn − 1 }.Если α — примитивный элемент поля GF (q), то любой другойпримитивный элемент может быть получен как степень αk , гдеk — целое взаимно простое с q − 1 ⇒ количествопримитивных элементов поля Fnp равно ϕ(pn − 1).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКак найти примитивные элементы поля23 / 71Fnp ?f (x) — примитивный элемент (генератор) группы Fn∗p , еслиipn −11= 1 и f (x) 6= 1 для 0 < i < pn − 1,f (x)2для любого многочлена g(x) ∈ Fn∗p найдётся степень iiтакая, что g(x) = f (x) , i ∈ { 0, 1, . .
. , pn − 1 }.Если α — примитивный элемент поля GF (q), то любой другойпримитивный элемент может быть получен как степень αk , гдеk — целое взаимно простое с q − 1 ⇒ количествопримитивных элементов поля Fnp равно ϕ(pn − 1).Например, в 9-элементном поле F23 имеется ϕ(8) = 4примитивных элемента, образованных степенями 1, 3, 5, 7(числа, взаимно простые с 8) уже найденного генератора:x + 1, (x + 1)3 = 2x + 1, (x + 1)5 = 2x + 2, (x + 1)7 = x + 2.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаЯ что-то не понимаю: неприводимые многочлены — этопримитивные элементы?24 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаЯ что-то не понимаю: неприводимые многочлены — этопримитивные элементы?Ведь было: для поиска и тех, и других нет эффективныхалгоритмов...24 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаЯ что-то не понимаю: неприводимые многочлены — этопримитивные элементы?Ведь было: для поиска и тех, и других нет эффективныхалгоритмов...Неприводимые многочлены ищут в кольце многочленовFp [x] над простым полем Fp — например, чтобыпостроить его расширение.24 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаЯ что-то не понимаю: неприводимые многочлены — этопримитивные элементы?Ведь было: для поиска и тех, и других нет эффективныхалгоритмов...Неприводимые многочлены ищут в кольце многочленовFp [x] над простым полем Fp — например, чтобыпостроить его расширение.Примитивные элементы ищут в мультипликативной группеnFn∗p расширения Fp — например, чтобы иметь удобноепредставление её элементов через степени генераторов.24 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаЯ что-то не понимаю: неприводимые многочлены — этопримитивные элементы?Ведь было: для поиска и тех, и других нет эффективныхалгоритмов...Неприводимые многочлены ищут в кольце многочленовFp [x] над простым полем Fp — например, чтобыпостроить его расширение.Примитивные элементы ищут в мультипликативной группеnFn∗p расширения Fp — например, чтобы иметь удобноепредставление её элементов через степени генераторов.Замечание: в поле GF (q) понятие «неприводимыймногочлен» не имеет смысла: там любой многочлен делится налюбой ненулевой...x+1Например, в F3 [x]/ x2 + 1 := x.2x + 124 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаМожет ли приводимый многочлен быть примитивнымэлементом?25 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаМожет ли приводимый многочлен быть примитивнымэлементом?F2= { 0, 1 }.1Возьмём поле2Возьмём неприводимый над345F2многочлен x3 + x + 1.Построим поле F = F2 [x]/ x3 + x + 1 ∼= F32 ; оносодержит все полиномы из F2 [x] степени не выше 2.Многочлен P (x) = x2 + x — приводим в любом кольце, вт.ч. в F2 [x], и он принадлежит F .Является ли P (x) — примитивным элементом поля F ?25 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаМожет ли приводимый многочлен быть примитивнымэлементом?F2= { 0, 1 }.1Возьмём поле2Возьмём неприводимый над345F2многочлен x3 + x + 1.Построим поле F = F2 [x]/ x3 + x + 1 ∼= F32 ; оносодержит все полиномы из F2 [x] степени не выше 2.Многочлен P (x) = x2 + x — приводим в любом кольце, вт.ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
