AA3-1(GF-I) (1127138), страница 2
Текст из файла (страница 2)
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПервые 99 значений ϕ(·) и степени генератора10 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПервые 99 значений ϕ(·) и степени генератораПусть вF∗pα — генератор; α−1 =?10 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПервые 99 значений ϕ(·) и степени генератораПусть вF∗pα — генератор; α−1 =?αp−1 = 1 ⇒ αp = α1 = α и α−1 = α−1 · αp−1 = αp−2 .Например, вF5 :α−1 =10 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаПервые 99 значений ϕ(·) и степени генератораПусть вF∗pα — генератор; α−1 =?αp−1 = 1 ⇒ αp = α1 = α и α−1 = α−1 · αp−1 = αp−2 .Например, вF5 :α−1 = α3 .10 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКак найти примитивные элементы поля11 / 71Fp ?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКак найти примитивные элементы поляЕсли примарное разложение (p − 1) —11 / 71Fp ?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКак найти примитивные элементы поля11 / 71Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffαk 6≡p 1 для каждого делителя k числа p − 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКак найти примитивные элементы поля11 / 71Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffαk 6≡p 1 для каждого делителя k числа p − 1.неизвестно — эффективного алгоритма не найдено(используют таблицы, вероятностныеалгоритмы...).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКак найти примитивные элементы поля11 / 71Fp ?Если примарное разложение (p − 1) —известно — элемент α ∈ Fp будет примитивным iffαk 6≡p 1 для каждого делителя k числа p − 1.неизвестно — эффективного алгоритма не найдено(используют таблицы, вероятностныеалгоритмы...).Если α — примитивный элемент поля Fp , то любой другой егопримитивный элемент может быть получен как степень αk , гдеk — целое число, взаимно простое с p − 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаНеприводимые многочленыУтверждениеКольцо многочленов k[x] над полем k — евклидово.ТеоремаКаждый элемент евклидова кольца однозначно с точностью доперестановок разлагается в произведение простых(неразложимых) элементов.Простые (неразложимые) элементы k[x] — неприводимыемногочлены.Вопросы для полей:1какие многочлены над ними неприводимы?2как находить неприводимые многочлены?12 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надC, R и Q:13 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надв полеCC, R и Q:— только многочлены 1-й степени;13 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надC, R и Q:в полеC— только многочлены 1-й степени;в полеR—1многочлены 1-й степени,2многочлены 2-й степени с отрицательнымдискриминантом;13 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены над13 / 71C, R и Q:в полеC— только многочлены 1-й степени;в полеR—в полеQ1многочлены 1-й степени,2многочлены 2-й степени с отрицательнымдискриминантом;— существуют неприводимые многочленыпроизвольной степени.Далеенасбудутинтересоватьмногочлены в конечных полях.неприводимыеПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надF2ПримерДано: поле F2 = h {0, 1}, +2 , ·2 i.Требуется: найти все неприводимые многочлены степеней2, 3, 4 над ним.14 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надF2ПримерДано: поле F2 = h {0, 1}, +2 , ·2 i.Требуется: найти все неприводимые многочлены степеней2, 3, 4 над ним.Вторая степень: x2 + ax + bЯсно, что b = 1, иначе x2 + ax = x(x + a) ⇒ ищемнеприводимый многочлен в виде x2 + ax + 1.14 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надF2ПримерДано: поле F2 = h {0, 1}, +2 , ·2 i.Требуется: найти все неприводимые многочлены степеней2, 3, 4 над ним.Вторая степень: x2 + ax + bЯсно, что b = 1, иначе x2 + ax = x(x + a) ⇒ ищемнеприводимый многочлен в виде x2 + ax + 1.Еслиa = 0, то x2 + 1 = (x + 1)2 ;a = 1, то получаем неприводимый многочлен.∴ над F2 существует единственный неприводимый многочленстепени 2: x2 + x + 1.14 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надF2Третья степень: x3 + ax2 + bx + 1(почему свободный член не равен нулю?)Исключая, как сделано ранее, делимость на x + 1, получаемусловие a + b 6= 0, т.е.a = 0, b = 1 ,a = 1, b = 0 .15 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надF2Третья степень: x3 + ax2 + bx + 1(почему свободный член не равен нулю?)Исключая, как сделано ранее, делимость на x + 1, получаемусловие a + b 6= 0, т.е.a = 0, b = 1 ,a = 1, b = 0 .∴ надF2 существует два неприводимых многочлена степени 3:x3 + x2 + 1 и x3 + x + 1 .15 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надF2Четвёртая степень: x4 + ax3 + bx2 + cx + 1Исключение делимости на x + 1 приводит к условию a + b + c = 1,т.е. имеется 4 варианта, которые дают 3 решения:a0011b0101c1001многочленx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1— приводимыйОткуда взялся ещё один приводимый многочлен?16 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаНеприводимые многочлены надF2Четвёртая степень: x4 + ax3 + bx2 + cx + 1Исключение делимости на x + 1 приводит к условию a + b + c = 1,т.е.
имеется 4 варианта, которые дают 3 решения:a0011b0101c1001многочленx4 + x + 1x4 + x2 + 1x4 + x3 + 1x4 + x3 + x2 + x + 1— приводимыйОткуда взялся ещё один приводимый многочлен?Найдены многочлены, у которых нет линейных делителей(степени 1). Но многочлен 4-й степени может разлагаться впроизведение двух неприводимых многочленов 2-й степени:x4 + x2 + 1 = (x2 + x + 1)2 .16 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаНеприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленов17 / 71F3 [x].ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа17 / 71Неприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы?F3 [x].ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа17 / 71Неприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленовМногочлены порядка 1:x2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!F3 [x].ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа17 / 71Неприводимые многочлены над F3Поле F3 = {0, 1, 2}, +3 , ·3 ⇒ кольцо многочленовМногочлены порядка 1:xF3 [x].2xx+12x + 1x+22x + 2Какие из них неприводимы? Все!Неприводимые многочлены порядка 2 вкорней 0, 1, 2):F3 [x] (они не имеютx2 + 12x2 + 2x2 + x + 22x2 + x + 1x2 + 2x + 22x2 + 2x + 1ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа18 / 71Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.FpсуществуетПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа18 / 71Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.— докажем позже.FpсуществуетПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа18 / 71Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fpсуществует— докажем позже.ВопросКак в кольцеFp [x]найти неприводимый многочлен?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа18 / 71Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fpсуществует— докажем позже.ВопросКак в кольцеFp [x]найти неприводимый многочлен?Ответ: нет эффективных алгоритмовПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа18 / 71Существование и нахождение неприводимых многочленовТеорема (о существовании неприводимых многочленов)Для любых натурального n и простого p наднеприводимый многочлен степени n.Fpсуществует— докажем позже.ВопросКак в кольцеFp [x]найти неприводимый многочлен?Ответ: нет эффективных алгоритмов(из таблиц, алгоритм из 5-й главы «Алгебры» Ван дерВардена, алгоритм Берлекэмпа...)ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
