AA3-1(GF-II) (1127139), страница 4
Текст из файла (страница 4)
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-1412Проверить, что F = F7 [x]/ x2 + x − 1 является полем.Выразить обратный к 1 − x в F в базисе 1, x .47 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-1412Проверить, что F = F7 [x]/ x2 + x − 1 является полем.Выразить обратный к 1 − x в F в базисе 1, x .Решение¶ a(x) = x2 + x − 1, a(0) = 6, a(1) = 1, a(2) = 5, a(3) = 4,a(4) = 6, a(5) = 1, a(6) = 6 ⇒многочлен a(x) — неприводим в F7 и F — поле ( ∼= F27 ).47 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениями47 / 78Задача ПГ-1412Проверить, что F = F7 [x]/ x2 + x − 1 является полем.Выразить обратный к 1 − x в F в базисе 1, x .Решение¶ a(x) = x2 + x − 1, a(0) = 6, a(1) = 1, a(2) = 5, a(3) = 4,a(4) = 6, a(5) = 1, a(6) = 6 ⇒многочлен a(x) — неприводим в F7 и F — поле ( ∼= F27 ).·F27 = ax + b | a, b ∈ F7 , x2 = 1 − x = 6x + 1(ax + b) · (6x + 1) = . . . = (2a + 6b)x + (6a + b) = 16a + b = 1a=1⇒a + 3b = 0b=2Проверка: (6x + 1)(x + 2) = 6x2 + 13x + 2 = 1 + 7x = 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-15Найти порядок элемента x + x2 в мультипликативной группе1 поля F [x]/ x4 + x + 1 ;22 поля F [x]/ x4 + x3 + 1 .248 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-15Найти порядок элемента x + x2 в мультипликативной группе1 поля F [x]/ x4 + x + 1 ;22 поля F [x]/ x4 + x3 + 1 .2Решениеx + x2 = x(x + 1)¶ x4 = x + 1(x2 + x)2 = x4 + x2 = x2 + x + 1,(x2 + x)3 = x(x + 1)(x2 + x + 1) = x(x3 + 1) == x4 + x = x + 1 + x = 1.Ответ: 3.48 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-15...Решение· x4 = x3 + 1(x2 + x)2 = x4 + x2 = x3 + x2 + 1,(x2 + x)3 = x(x + 1)(x3 + x2 + 1) = x(x4 + x2 + x + 1) == x(x3 + x2 + x) = x4 + x3 + x2 = x2 + 1,(x2 + x)4 = (x2 + x)(x2 + x)3 = (x2 + x)(x2 + 1) == x4 + x2 + x3 + x = x3 + 1 + x2 + x3 + x == x2 + x + 1,...— долго и сложно49 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-15...α4 = α3 + 1, x = α, β = α2 + αРешениеα4 = α3 + 1α5 = α4 + α = α3 + α + 1α6 = α2 (α3 + 1) = α3 + α2 + α + 1α7 = α4 + α3 + α2 + α = α2 + α + 1α8 = α3 + α2 + αα9 = α4 + α3 + α2 = α2 + 1α10 = α3 + 1α11 = α4 + α2 = α3 + α2 + 1α12 = α4 + α3 + α = α + 1α13 = α2 + α = β. 13 6 |15 ⇒ deg β = 1550 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-16Найти количество неприводимых многочленов123F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .степени 7 над полем51 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями51 / 78Задача ПГ-16Найти количество неприводимых многочленов123F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .степени 7 над полемРешениеPmdm = pnm|n1d7 =?Pmdm = 27 = 1 · d1 + 7 · d7 = 128.m|7d1 = 2 (x, x + 1) ⇒ d7 = (128 − 2)/7 = 126/7 = 18.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями52 / 78Задача ПГ-17Чему равно произведение всех ненулевых элементов поляF62 ?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями52 / 78Задача ПГ-17Чему равно произведение всех ненулевых элементов поляРешениеВсе ненулевые элементы поля6 −1x2F62 ?F62 являются корнями уравнения− 1 = x63 − 1 = 0 .По теореме Виета их произведение равно свободному члену,т.е. −1 ≡2 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-18Чему равна сумма всех элементов поляF73 ?53 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями53 / 78Задача ПГ-18Чему равна сумма всех элементов поляРешениеВсе элементы поляF73 ?F73 являются корнями уравнения7x3 − x = x2187 − x = 0 .(∗)По теореме Виета их сумма равна коэффициенту перед x2186 ,т.е. 0.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-19Для поля F = F3 [x]/ −2x2 + x + 2 построить таблицусоответствий между полиномиальным и степеннымпредставлением для ненулевых элементов.С помощью данной таблицы вычислить выражение1(2x)7 (2)−.2x + 1 (x)9 (x + 2)54 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями54 / 78Задача ПГ-19Для поля F = F3 [x]/ −2x2 + x + 2 построить таблицусоответствий между полиномиальным и степеннымпредставлением для ненулевых элементов.С помощью данной таблицы вычислить выражение1(2x)7 (2)−.2x + 1 (x)9 (x + 2)Решениеchar F = 3, поэтому −2x2 + x + 2 ≡3 x2 + x + 2 = a(x).F ∗ содержит 32 − 1 = 8 элементов и все они могут бытьпредставлены как степени αi , i = 1, 8 примитивного элемента α.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениями54 / 78Задача ПГ-19Для поля F = F3 [x]/ −2x2 + x + 2 построить таблицусоответствий между полиномиальным и степеннымпредставлением для ненулевых элементов.С помощью данной таблицы вычислить выражение1(2x)7 (2)−.2x + 1 (x)9 (x + 2)Решениеchar F = 3, поэтому −2x2 + x + 2 ≡3 x2 + x + 2 = a(x).F ∗ содержит 32 − 1 = 8 элементов и все они могут бытьпредставлены как степени αi , i = 1, 8 примитивного элемента α.Если элемент x окажется примитивным, то положим α = x и,поскольку вычисления в F23 проводятся по mod a(x), будемиметь x2 + x + 2 = 0 ⇒ x2 = −x − 2 = 2x + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-19... x2 = 2x + 1,F3 [x]РешениеНайдём порядок элемента x ⇒ проверим степени, являющиесяделителями 8, т.е. 2 и 4:x2 = 2x + 1 6= 1,x4 = 2 6= 1— т.е. x — примитивный элемент F .Повезло: a(x) = x2 + x + 2 оказался примитивным многочленомнад F3 (т.е. a(x) | x8 + 1 и a(x) 6 | xt + 1, t = 3, . . . , 7), иначегенератор F пришлось бы искать.55 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-19... x2 = 2x + 1,F3 [x]РешениеНайдём порядок элемента x ⇒ проверим степени, являющиесяделителями 8, т.е. 2 и 4:x2 = 2x + 1 6= 1,x4 = 2 6= 1— т.е. x — примитивный элемент F .Повезло: a(x) = x2 + x + 2 оказался примитивным многочленомнад F3 (т.е. a(x) | x8 + 1 и a(x) 6 | xt + 1, t = 3, . . . , 7), иначегенератор F пришлось бы искать.Теперь вычислим значение выражения ( 28 = 256 ≡3 1):x7x8 x7 x81(2x)7 (2)1−= 2 − 9 6 = 2 − 15 =92x + 1 (x) (x + 2)xx xxx6= x − 1 = x + 2 − 1 = x + 1.55 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-20Для поля F = F3 [x]/ x2 + 1 ∼= F23 построить таблицусоответствий между полиномиальным и степеннымпредставлением для всех ненулевых элементов поля.56 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями56 / 78Задача ПГ-20Для поля F = F3 [x]/ x2 + 1 ∼= F23 построить таблицусоответствий между полиномиальным и степеннымпредставлением для всех ненулевых элементов поля.РешениеВ данном 9-элементном поле x2 + 1 = 0 ⇒ x2 = −1 ≡3 2.1. Найдём порядок элемента x ⇒ проверим степени,являющиеся делителями 9 − 1 = 8, т.е.
2 и 4:x2 = 2, x4 = 1.Следовательно, элемент deg x = 4 и x не являетсягенератором группы F ∗ ( x4 − 1 = x4 + 2 = (x2 + 1)(x2 + 2) иx2 + 1 — не есть примитивный многочлен над F3 ).Также не являются примитивными все степени x:x2 = 2, x3 = 2x, x4 = 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-20...x2 ≡3 22. Найдём порядок элемента x + 1:(x + 1)2 = x2 + 2x + 1 = 2x, (x + 1)4 = (2x)2 = 2,т.е. α = x + 1 оказался примитивным элементом.57 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-20...x2 ≡3 22. Найдём порядок элемента x + 1:(x + 1)2 = x2 + 2x + 1 = 2x, (x + 1)4 = (2x)2 = 2,т.е. α = x + 1 оказался примитивным элементом.Его степени:α1 = x + 1,α5 = 2(x + 1) = 2x + 2,α2 = 2x,α6 = α2 · α4 = x,α3 = 2x(x + 1) = 2x + 1,α7 = x(x + 1) = x + 2,α4 = 2,α8 = (α4 )2 = 1.Заметим, что вычисление очередной степени αi+j частобывает удобным провести как αi · αj , а не как α · αi+j−1 .57 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-21В факторкольце F3[x]/ x4 + 1 найти все элементы главногоидеала x2 + x + 2 .58 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-21В факторкольце F3[x]/ x4 + 1 найти все элементы главногоидеала x2 + x + 2 .Решение1. Сначала проверим, является ли многочленf (x) = x2 + x + 2 делителем x4 + 1?58 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-21В факторкольце F3[x]/ x4 + 1 найти все элементы главногоидеала x2 + x + 2 .Решение1.
Сначала проверим, является ли многочленf (x) = x2 + x + 2 делителем x4 + 1?x4 + 1 = (x2 + x + 2) · (x2 + 2x + 2) — да!Поэтому искомый идеал составят многочлены кольца (т.е.степени не выше 3), кратные f (x):x2 + x + 2 = (x2 + x + 2)(ax + b) | a, b ∈ F3 .Проведём умножение:(x2 + x + 2) · (ax + b) = ax3 + (a + b)x2 + (2a + b)x + 2b.58 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-21...2.
Теперь, перебирая все возможные значенияa, b ∈ F3 ,найдём все элементы идеала x2 + x + 2 :a000111222b012012012ax3 + (a + b)x2 + (2a + b)x + 2b0x2 + x + 22x2 + 2x + 1x3 + x2 + 2xx3 + 2x2 + 2x3 + x + 12x3 + 2x2 + x2x3 + 2x + 22x3 + x2 + 159 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-22В полеF7 [x]/ x4 + x3 + x2 + 3 найти обратный к элемент.60 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями60 / 78Задача ПГ-22В полеF7 [x]/ x4 + x3 + x2 + 3 найти обратный к элемент.РешениеОбратный элемент к x2 + x + 3 находим, решая уравнение(x4 + x3 + x2 + 3) · χ(x) +(x2 + x + 3) · y(x) = 1|{z}(∗)=0с помощью расширенного алгоритма Евклида: им будет y(x).Замечание: вычислять коэффициент при x4 + x3 + x2 + 3(χi (x)) нет необходимости.ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
