Конечные поля (часть 2) (1127161), страница 5
Текст из файла (страница 5)
13 6 |15 ⇒ deg β = 1557 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-16Найти количество неприводимых многочленов123F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .степени 7 над полем58 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями58 / 86Задача ПГ-16Найти количество неприводимых многочленов123F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .степени 7 над полемРешение.Pmdm = pnm|n¶ d7 надF2Pmdm = 27 = 1 · d1 + 7 · d7 = 128.m|7d1 = 2 : (x, x + 1) ⇒ d7 = (128 − 2)/7 = 126/7 = 18.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями59 / 86Задача ПГ-16...· d6 надF561 X1 µ(d) 5 d =µ(1)56 + µ(2)53 + µ(3)52 + µ(6)5 =66d6 =d|6=¸ d24 над115480[ 15625 − 125 − 25 + 5 ] == 2580 .66F3241 X1 µ(d) 3 d =µ(1)324 + µ(2)312 + µ(3)318 +2424d|24+µ(4)36 + µ(6)34 + µ(8)33 + µ(12)32 + µ(24)3 =d24 ==324 − 312 − 318 + 343486718792== 11767675923 .2424ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями60 / 86Задача ПГ-17Чему равно произведение всех ненулевых элементов поляF62 ?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями60 / 86Задача ПГ-17Чему равно произведение всех ненулевых элементов поляРешение.Все ненулевые элементы поля6 −1x2F62 ?F62 являются корнями уравнения− 1 = x63 − 1 = 0 .По теореме Виета их произведение равно свободному члену,т.е.
−1 ≡2 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями61 / 86Задача ПГ-18Чему равна сумма всех элементов поляF73 ?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями61 / 86Задача ПГ-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)62 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями62 / 86Задача ПГ-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Задачи с решениями62 / 86Задача ПГ-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,63 / 86F3 [x]Найдём порядок элемента x: т.к.
8 = 23 ,равенство x4 = 1:82= 4, проверимx4 = (x2 )2 = (2x + 1)2 = x2 + x + 1 = 6 2x + 1+ 6 x + 1 = 2 6= 1,т.е. x — примитивный элемент F .Повезло: a(x) = x2 + x + 2 оказался примитивным многочленомнад F3 , иначе генератор F пришлось бы искать.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-19... x2 = 2x + 1,63 / 86F3 [x]Найдём порядок элемента x: т.к. 8 = 23 ,равенство x4 = 1:82= 4, проверимx4 = (x2 )2 = (2x + 1)2 = x2 + x + 1 = 6 2x + 1+ 6 x + 1 = 2 6= 1,т.е. x — примитивный элемент F .Повезло: a(x) = x2 + x + 2 оказался примитивным многочленомнад F3 , иначе генератор F пришлось бы искать.Теперь вычислим значение выражения ( 28 = 256 ≡3 1):1(2x)7 (2)1x7x8 x7 x8−=−=− 15 =2x + 1 (x)9 (x + 2)x2 x9 x6x2x62 33= x − 1 = (x ) + 2 = (2x + 1) + 2 = 2x3 + 1 + 2 == 2(2x2 + x) + 3 = x2 + 2x + 3 = 2x + 1 + 2x + 3 = x + 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-20Для поля F = F3 [x]/ x2 + 1 ∼= F23 построить таблицусоответствий между полиномиальным и степеннымпредставлением для всех ненулевых элементов поля.64 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями64 / 86Задача ПГ-20Для поля F = F3 [x]/ x2 + 1 ∼= F23 построить таблицусоответствий между полиномиальным и степеннымпредставлением для всех ненулевых элементов поля.Решение.В данном 9-элементном поле x2 + 1 = 0 ⇒ x2 = −1 ≡3 2.1. Найдём порядок элемента x, для чего проверим равенствоx4 = 1 (т.к.
9 − 1 = 8 = 23 , 28 = 4): (x2 )4 = 4 ≡3 1.Следовательно, deg x = 4 и элемент x не являетсягенератором группы F ∗ (и x2 + 1 — не есть примитивныймногочлен над F3 : x4 − 1 = x4 + 2 = (x2 + 1)(x2 + 2)).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-20...65 / 86x2 ≡3 22. Найдём (x + 1)4 :(x+1)4 = (x+1)(x+1)3 = (x+1)(x3 +1) = (x+1)(2x+1) == 2x2 + 6 x+ 6 2x + 1 = 4 + 1 = 2 6= 1т.е. α = x + 1 оказался примитивным элементом.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-20...65 / 86x2 ≡3 22. Найдём (x + 1)4 :(x+1)4 = (x+1)(x+1)3 = (x+1)(x3 +1) = (x+1)(2x+1) == 2x2 + 6 x+ 6 2x + 1 = 4 + 1 = 2 6= 1т.е. α = 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 .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями66 / 86Задача ПГ-21В фактор-кольце F3 [x]/ x4 + 1 найти все элементы главногоидеала x2 + x + 2 .ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями66 / 86Задача ПГ-21В фактор-кольце F3 [x]/ x4 + 1 найти все элементы главногоидеала x2 + x + 2 .Решение.1. Сначала проверим, является ли многочленf (x) = x2 + x + 2 делителем x4 + 1?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями66 / 86Задача ПГ-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.ПРИКЛАДНАЯ АЛГЕБРА.
Часть 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 + 167 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-22В полеF7 [x]/ x4 + x3 + x2 + 3 найти обратный к элемент.68 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями68 / 86Задача ПГ-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).Замечание: вычислять полином χi (x) нет необходимости.(∗)ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями69 / 86Задача ПГ-22x4 + x3 + x2 + 3, // Инициализацияx2 + x + 3,0,1.Шаг 0.r−2 (x)r−1 (x)y−2 (x)y−1 (x)Шаг 1.r−2 (x) = r−1 (x)q0 (x) + r0 (x),// Делим r−2 (x) на r−1 (x) с остаткомq0 (x) = x2 + 5,r0 (x) = 2x + 2,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = −x2 − 5.Шаг 2.r−1 (x) = r0 (x)q1 (x) + r1 (x),// Делим r−1 (x) на r0 (x) с остаткомq1 (x) = 4x,r1 (x) = 3,y1 (x) = y−1 (x) − y0 (x)q1 (x) = 1 + 4x(x2 + 5) =====ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-22Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена вправой части (∗): 1 — многочлен 0-й степени.70 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-22Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена вправой части (∗): 1 — многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.70 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-22Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена вправой части (∗): 1 — многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Чтобы найти y(x), нужно домножить y1 (x) на 3−1 = 5:y(x) = 5y1 (x) = 5 · (4x3 + 6x + 1) = 6x3 + 2x + 5.70 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями70 / 86Задача ПГ-22Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена вправой части (∗): 1 — многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Чтобы найти y(x), нужно домножить y1 (x) на 3−1 = 5:y(x) = 5y1 (x) = 5 · (4x3 + 6x + 1) = 6x3 + 2x + 5.Проверка: y(x)(x2 + x + 3) = (6x3 + 2x + 5)(x2 + x + 3) == 6x5 + 6x4 + 6x3 + 4x + 1 == 6x(−x3 − x2 − 3) + 6x4 + 6x3 + 4x + 1 = 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями71 / 86Задача ПГ-23В поле F =F5 [x]/ x2 + 3x + 3 найти обратную к матрицеM =3x + 4 x + 2x + 3 3x + 2.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями71 / 86Задача ПГ-23В поле F =F5 [x]/ x2 + 3x + 3 найти обратную к матрицеM =3x + 4 x + 2x + 3 3x + 2.Решение.Для матриц размера 2×2 обратная матрица записывается ввиде−11a bd −b=.c dad − bc −c a1. Сначала вычислим det M = ad − bc с учётом x2 = 2x + 2:det M = (3x+4)(3x+2)−(x+2)(x+3) = 4x2 +3x+3−x2 −1 == 3x2 + 3x + 2 = 3(2x + 2) + 3x + 2 = 4x + 3.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-23...2.
Найдём обратный к 4x + 3 элемент, решая уравнение(x2 + 3x + 3) · χ(x) + (4x + 3) · y(x) = 1.с помощью расширенного алгоритма Евклида:Шаг 0.Шаг 1.r−2 (x) = x2 + 3x + 3, // Инициализацияr−1 (x) = 4x + 3,y−2 (x) = 0,y−1 (x) = 1.r−2 (x) = r−1 (x)q0 (x) + r0 (x),// Делим r−2 (x) на r−1 (x) с остаткомq0 (x) = 4x + 4,r0 (x) = 1,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) == −4x − 4 = x + 1.Т.е. (4x + 3)−1 = y0 (x) = x + 1.72 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-23... x2 ≡5 2x + 23. Вычислим обратную матрицу3x + 2 4x + 3x+3 1−1M= (x + 1)=.4x + 2 3x + 44x3x73 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями73 / 86Задача ПГ-23... x2 ≡5 2x + 23.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
