Конечные поля (часть 2) (1127161), страница 6
Текст из файла (страница 6)
Вычислим обратную матрицу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 1ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями74 / 86Задача ПГ-24Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈F2 [x].ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями74 / 86Задача ПГ-24Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈F2 [x].Решение.1. Сначала пытаемся найти корни f (x) в F2 : получимf (0) = f (1) = 1, и значит f (x) не имеет корней в F2 т.е.
неимеет линейных множителей.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями74 / 86Задача ПГ-24Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈F2 [x].Решение.1. Сначала пытаемся найти корни f (x) в F2 : получимf (0) = f (1) = 1, и значит f (x) не имеет корней в F2 т.е. неимеет линейных множителей.2. Далее ищем делители f (x) среди неприводимыхмногочленов степени 2.Таковых над F2 только один — x2 + x + 1.При делении f (x) на x2 + x + 1, получаем9876432f (x) = (x2 + x + 1)(x| + x + x + x +{zx + x + x + x + 1}).g(x)ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями75 / 86Задача ПГ-24...Делим частное g(x) на 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.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями75 / 86Задача ПГ-24...Делим частное g(x) на 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 =65= (x3 + x + 1)(xx3 + x2 + 1})| + x +{zh(x)— делится!ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями76 / 86Задача ПГ-24...Производя далее попытки деления h(x) на многочлены 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Задачи с решениями76 / 86Задача ПГ-24...Производя далее попытки деления h(x) на многочлены 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Задачи с решениями76 / 86Задача ПГ-24...Производя далее попытки деления h(x) на многочлены 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] раскладывается налинейные множители.В данном поле найти все корни данного многочлена.77 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями77 / 86Задача ПГ-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) ∈ F23 .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями78 / 86Задача ПГ-25...2.
Известно, что если g(x) — неприводимый многочлен степениn над Fp , то он:ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями78 / 86Задача ПГ-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Задачи с решениями78 / 86Задача ПГ-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 = α + 179 / 86F3Действительно (подчёркиваем слагаемые, дающие в сумме 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 = α + 179 / 86F3Действительно (подчёркиваем слагаемые, дающие в сумме 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...80 / 86F34. Определить корни многочленаg(x) = (x − α)(x − 2α − 1) вполе F3 [x]/ x2 + 2x + 2 легко:ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-25...80 / 86F34. Определить корни многочленаg(x) = (x − α)(x − 2α − 1) вполе F3 [x]/ x2 + 2x + 2 легко:всегда можно взять α = x,откуда второй корень α3 = 2α + 1 = 2x + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-25...80 / 86F34. Определить корни многочленаg(x) = (x − α)(x − 2α − 1) вполе F3 [x]/ x2 + 2x + 2 легко:всегда можно взять α = x,откуда второй корень α3 = 2α + 1 = 2x + 1.5. Таким образом, в поле F3 [x]/ x2 + 2x + 2 ∼= GF (32 )многочленf (x) = x3 + x + 2 имеет корни2, x и 2x + 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями81 / 86Задача ПГ-26...Найти минимальный многочлен m(x) ∈ F5 [x], который имееткорень α3 , где α — примитивный элемент поляF = F5 [x]/ x2 + x + 2 .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями81 / 86Задача ПГ-26...Найти минимальный многочлен m(x) ∈ F5 [x], который имееткорень α3 , где α — примитивный элемент поляF = F5 [x]/ x2 + x + 2 .Решение.1. Известно, что минимальный многочлен m(x) в полехарактеристики 5 вместе с корнем α3 содержит все смежные с23ним (α3 )5 = α15 , (α3 )5 = α75 , (α3 )5 = α375 и т.д.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями81 / 86Задача ПГ-26...Найти минимальный многочлен m(x) ∈ F5 [x], который имееткорень α3 , где α — примитивный элемент поляF = F5 [x]/ x2 + x + 2 .Решение.1. Известно, что минимальный многочлен m(x) в полехарактеристики 5 вместе с корнем α3 содержит все смежные с23ним (α3 )5 = α15 , (α3 )5 = α75 , (α3 )5 = α375 и т.д.22. В поле F будет α5 −1 = α24 = 1 ⇒ смежный класс,образованный α3 содержит только два элемента α3 и α15(т.к. α75 = α24·3+3 = α3 ) ⇒ минимальный многочлен m(x)имеет степень 2 и может быть представлен какm(x) = (x − α3 )(x − α15 ) = x2 − (α3 + α15 )x + α18 .ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-26...m(x) = x2 − (α3 + α15 )x + α183. Найдём коэффициенты многочлена m(x) учётомα2 = −α − 2 = 4α + 3:α3 = α · α2 = α(4α + 3) = 4α2 + 3α == 4(4α + 3) + 3α = 4α + 2,α15 = (α3 )5 = (4α + 2)5 = 4α5 + 2 == 4α2 α3 + 2 = 4(4α + 3)(4α + 2) + 2 == 4(α2 + 1) + 2 = 4(4α + 4) + 2 = α + 3,α3 + α15 = 4α + 2 + α + 3 = 0,α18 = α3 α15 = (4α + 2)(α + 3) == 4(4α + 3) + 4α + 1 = 3.82 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-26...m(x) = x2 − (α3 + α15 )x + α183.
Найдём коэффициенты многочлена m(x) учётомα2 = −α − 2 = 4α + 3:α3 = α · α2 = α(4α + 3) = 4α2 + 3α == 4(4α + 3) + 3α = 4α + 2,α15 = (α3 )5 = (4α + 2)5 = 4α5 + 2 == 4α2 α3 + 2 = 4(4α + 3)(4α + 2) + 2 == 4(α2 + 1) + 2 = 4(4α + 4) + 2 = α + 3,α3 + α15 = 4α + 2 + α + 3 = 0,α18 = α3 α15 = (4α + 2)(α + 3) == 4(4α + 3) + 4α + 1 = 3.В итоге:m(x) = x2 + 3.82 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-27Решить уравнение f (x) = x3 + 3x2 + 4x + 4 = 0, еслиf (x) ∈ F5 [x].83 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями83 / 86Задача ПГ-27Решить уравнение f (x) = x3 + 3x2 + 4x + 4 = 0, еслиf (x) ∈ F5 [x].Решение.Вычисляем значения f (x) для x ∈ GF (5) = { 0, 1, 2, 3, 4 }:f (0) = 4, f (1) = 2, f (2) = 1, f (3) = 0.Таким образом, x = 3 — корень f (x).Деля «уголком» f (x) на f1 (x) = x − 3 (или на x + 2 ),получим x3 + 3x2 + 4x + 4 = (x − 3) · (x2 + x + 2).Перебором элементов x ∈ GF (5) убеждаемсяf2 (x) = x2 + x + 2 — неприводимый многочлен.В поле F5 [x]/ x2 + x + 2 корни многочлена f2 (x) = 0 сутьx, x5и x2 = −x − 2 = 4x + 3.ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
