AA3-1(GF-II) (1127139), страница 5
Текст из файла (страница 5)
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями61 / 78Задача ПГ-22Шаг 0.Шаг 1.Шаг 2.r−2 (x) = x4 + x3 + x2 + 3, // Инициализацияr−1 (x) = x2 + x + 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) = x2 + 5,r0 (x) = 2x + 2,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = −x2 − 5.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) == 4x3 + 6x + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-22Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена вправой части (∗): 1 — многочлен 0-й степени.62 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-22Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена вправой части (∗): 1 — многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.62 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть 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.62 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть 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.Проверка: 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.62 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениями63 / 78Задача ПГ-23В поле F =F5 [x]/ x2 + 3x + 3 найти обратную для матрицыM =3x + 4 x + 2x + 3 3x + 2.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями63 / 78Задача ПГ-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.64 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-23... x2 ≡5 2x + 23. Вычислим обратную матрицу3x + 2 4x + 3x+3 1−1M= (x + 1)=.4x + 2 3x + 44x3x65 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-23... x2 ≡5 2x + 23. Вычислим обратную матрицу3x + 2 4x + 3x+3 1−1M= (x + 1)=.4x + 2 3x + 44x3xПроверка: 3x + 4 x + 2x+3 1×=x + 3 3x + 24x3x(3x + 4)(x + 3) + 4x(x + 2) 3x + 4 + 3x(x + 2)==(x + 3)2 + 4x(3x + 2)x + 3 + 3x(3x + 2)2x2 + x + 2 3x2 + 4x + 4==3x2 + 4x + 4 4x2 + 2x + 32(2x + 2) + x + 2 3(2x + 2) + 4x + 41 0==.3(2x + 2) + 4x + 4 4(2x + 2) + 2x + 30 165 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями66 / 78Задача ПГ-24Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈F2 [x].ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями66 / 78Задача ПГ-24Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈Решение1.
Сначала пытаемся найти корни f (x) вf (0) = 1,Значит, f (x) не имеет корней вмножителей.F2 [x].F2 :f (1) = 1.F2 т.е. не имеет линейныхПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями66 / 78Задача ПГ-24Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈Решение1. Сначала пытаемся найти корни f (x) вf (0) = 1,Значит, f (x) не имеет корней вмножителей.F2 [x].F2 :f (1) = 1.F2 т.е.
не имеет линейных2. Далее ищем делители f (x) среди неприводимыхмногочленов степени 2.Таковых над F2 только один — x2 + x + 1.При делении f (x) на x2 + x + 1, получаемf (x) = (x2 + x + 1)(x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-24...Продолжаем дальше делить на x2 + x + 1:g(x) = x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 == (x2 + x + 1)(x7 + x4 + x3 + x2 + x + 1) + x,т.е.
x2 + x + 1 — делитель f (x) кратности 1.67 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями67 / 78Задача ПГ-24...Продолжаем дальше делить на x2 + x + 1:g(x) = x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 == (x2 + x + 1)(x7 + x4 + x3 + x2 + x + 1) + x,т.е.
x2 + x + 1 — делитель f (x) кратности 1.3. Неприводимых многочленов степени 3 надx3 + x + 1 и x3 + x2 + 1.Пробуем поделить g(x) на x3 + x + 1:F2 два:x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 == (x3 + x + 1)(x6 + x5 + x3 + x2 + 1)— делится!ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями68 / 78Задача ПГ-24...Производя далее попытки деления h(x) = x6 + x5 + x3 + x2 + 1на многочлены 3-й степени, получаемx6 + x5 + x3 + x2 + 1 = (x3 + x + 1)(x3 + x2 + x + 1) + x2 ,x6 + x5 + x3 + x2 + 1 = (x3 + x2 + 1)x3 + x2 + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениями68 / 78Задача ПГ-24...Производя далее попытки деления h(x) = x6 + x5 + x3 + x2 + 1на многочлены 3-й степени, получаемx6 + x5 + x3 + x2 + 1 = (x3 + x + 1)(x3 + x2 + x + 1) + x2 ,x6 + x5 + x3 + x2 + 1 = (x3 + x2 + 1)x3 + x2 + 1.Т.к. как многочлен 6-ой степени h(x) не имеет делителей 3-йи меньших степеней, то он является неприводимым: если бы онимел делитель, скажем, степени 4, то у него был бы иделитель степени 6 − 4 = 2.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями68 / 78Задача ПГ-24...Производя далее попытки деления h(x) = x6 + x5 + x3 + x2 + 1на многочлены 3-й степени, получаемx6 + x5 + x3 + x2 + 1 = (x3 + x + 1)(x3 + x2 + x + 1) + x2 ,x6 + x5 + x3 + x2 + 1 = (x3 + x2 + 1)x3 + x2 + 1.Т.к.
как многочлен 6-ой степени h(x) не имеет делителей 3-йи меньших степеней, то он является неприводимым: если бы онимел делитель, скажем, степени 4, то у него был бы иделитель степени 6 − 4 = 2.В итоге вF2 [x] имеем разложениеf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 == (x2 + x + 1)(x3 + x + 1)(x6 + x5 + x3 + x2 + 1).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-25Найти минимальное поле характеристики 3, в котороммногочлен f (x) = x3 + x + 2 ∈ F3 [x] раскладывается налинейные множители.В данном поле найти все корни данного многочлена.69 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями69 / 78Задача ПГ-25Найти минимальное поле характеристики 3, в котороммногочлен f (x) = x3 + x + 2 ∈ F3 [x] раскладывается налинейные множители.В данном поле найти все корни данного многочлена.Решение1. Найдём разложение многочлена f (x) на неприводимыемножители над F3 .Проверяем корни: f (0) = 2, f (1) = 1, f (2) = 0.Т.к.
x − 2 ≡3 x + 1, то f (x) = (x + 1)(x2 + 2x + 2).Найдём разложение многочлена g(x) = x2 + 2x + 2 ∈ F3 [x].Он не имеет корней, его степень = 2 ⇒ он неприводим.Окончательно: f (x) = (x + 1)(x2 + 2x + 2).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями70 / 78Задача ПГ-25...2.
Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями70 / 78Задача ПГ-25...2. Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:в поле своего расширения F = Fp [x]/(g(x))раскладывается на n линейных множителей—2n−1ppg(x) = (x − α) · (x − α ) · x − α· . . .
· x − αp,где α – произвольный корень g(x) в F ;не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями70 / 78Задача ПГ-25...2. Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:в поле своего расширения F = Fp [x]/(g(x))раскладывается на n линейных множителей—2n−1ppg(x) = (x − α) · (x − α ) · x − α· . . . · x − αp,где α – произвольный корень g(x) в F ;не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.3.
Рассмотрим поле F3 [x]/(g(x)) расширения многочленаg(x) = x2 + 2x + 2.В этом поле если α — корень g(x), то и α3 — тоже корень.Вычисляем:α2 = −2α − 2 = α + 1 и α3 = α(α + 1) = α2 + α = 2α + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-25... α2 = α + 171 / 78F3Действительно (подчёркиваем слагаемые, дающие в сумме 0):(x − α)(x − 2α − 1) = (x + 2α) · (x + α + 2) == x2 + αx + 2x + 2αx + 2α2 + 4α == x2 + 2x + 2α + 2 + 4α = x2 + 2x + 2.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-25... α2 = α + 171 / 78F3Действительно (подчёркиваем слагаемые, дающие в сумме 0):(x − α)(x − 2α − 1) = (x + 2α) · (x + α + 2) == x2 + αx + 2x + 2αx + 2α2 + 4α == x2 + 2x + 2α + 2 + 4α = x2 + 2x + 2.Построенное расширение — поле F3 [x]/ x2 + 2x + 2 —содержит найденный ранее корень 2, поэтому многочлен f (x)в этом поле раскладывается на следующие линейныемножители:f (x) = x3 + x + 2 = (x − 2)(x − α)(x − 2α − 1) == (x + 1)(x + 2α)(x + α + 2).ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-25...72 / 78F34. Определить корни многочленаg(x) = (x − α)(x − 2α − 1) вполе F3 [x]/ x2 + 2x + 2 легко:ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-25...72 / 78F34. Определить корни многочленаg(x) = (x − α)(x − 2α − 1) вполе F3 [x]/ x2 + 2x + 2 легко:всегда можно взять α = x,откуда второй корень α3 = 2α + 1 = 2x + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-25...72 / 78F34. Определить корни многочленаg(x) = (x − α)(x − 2α − 1) вполе F3 [x]/ x2 + 2x + 2 легко:всегда можно взять α = x,откуда второй корень α3 = 2α + 1 = 2x + 1.5. Таким образом, в поле F3 [x]/ x2 + 2x + 2 многочленf (x) = x3 + x + 2 имеет корни2, x и 2x + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
