Лекции по прикладной алгебре. v2.0 (1127112), страница 11
Текст из файла (страница 11)
степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (∗): 1 — многочлен 0-й степени.Прикладная алгебраПоля ГалуаЗадачи137 / 432Решение (продолжение -2)Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (∗): 1 — многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Прикладная алгебраПоля ГалуаЗадачи137 / 432Решение (продолжение -2)Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (∗): 1 — многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Чтобы найти b(x), нужно домножить y1 (x) на 3−1 = 5:b(x) = 5y1 (x) = 5 · (4x3 + 6x + 1) = 6x3 + 2x + 5.Прикладная алгебраПоля ГалуаЗадачи137 / 432Решение (продолжение -2)Алгоритм заканчивает свою работу на Шаге 2, т.к.
степень 0очередного остатка r1 (x) = 3 равна степени многочлена в правойчасти (∗): 1 — многочлен 0-й степени.В результате работы алгоритма получено:(x2 + x + 3)(4x3 + 6x + 1) = r1 (x) = 3.Чтобы найти b(x), нужно домножить y1 (x) на 3−1 = 5:b(x) = 5y1 (x) = 5 · (4x3 + 6x + 1) = 6x3 + 2x + 5.Проверка: b(x)(x2 + x + 3) = (6x3 + 2x + 5)(x2 + x + 3) == 6x5 + 6x4 + 6x3 + 4x + 1 == 6x(−x3 − x2 − 3) + 6x4 + 6x3 + 4x + 1 = 1.Прикладная алгебраПоля ГалуаЗадачи138 / 432Задача (ПГ-21)В полеF25 = F5 [x]/(x2 + 3x + 3) найти обратную для матрицыM =3x + 4 x + 2x + 3 3x + 2.Прикладная алгебраПоля ГалуаЗадачи138 / 432Задача (ПГ-21)В полеF25 = 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.Прикладная алгебраПоля ГалуаЗадачи139 / 432Решение (продолжение -1)2.
Далее найдём обратный к 4x + 3 элемент решая уравнение(x2 + 3x + 3) · a(x) + (4x + 3) · b(x) = 1.с помощью расширенного алгоритма Евклида:Шаг 0. r−2 (x) = x2 + 3x + 3, // Инициализацияr−1 (x) = 4x + 3,y−2 (x) = 0,y−1 (x) = 1.Шаг 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 = b(x) = y0 (x) = x + 1.Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2;140 / 432x2 ≡5 2x + 2)3.
Наконец, вычислим обратную матрицу3x + 2 4x + 3x+3 1−1M= (x + 1)=.4x + 2 3x + 44x3xПрикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2;140 / 432x2 ≡5 2x + 2)3. Наконец, вычислим обратную матрицу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Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-22)Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈ F2 [x].141 / 432Прикладная алгебраПоля ГалуаЗадачи141 / 432Задача (ПГ-22)Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈ F2 [x].Решение1.
Сначала пытаемся найти корни f (x) вf(0) = 1,Значит, f (x) не имеет корней вмножителей.F2 :f(1) = 1.F2 т.е. не имеет линейныхПрикладная алгебраПоля ГалуаЗадачи141 / 432Задача (ПГ-22)Разложить на неприводимые множители многочленf (x) = x11 + x9 + x8 + x4 + x3 + x2 + 1 ∈ F2 [x].Решение1.
Сначала пытаемся найти корни f (x) вf(0) = 1,Значит, f (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).Прикладная алгебраПоля ГалуаЗадачи142 / 432Решение (продолжение -1)Продолжаем дальше делить на 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.Прикладная алгебраПоля ГалуаЗадачи142 / 432Решение (продолжение -1)Продолжаем дальше делить на 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 над F2 два: x3 + x + 1и x3 + x2 + 1. Пробуем поделить g(x) на x3 + x + 1:x9 + x8 + x7 + x6 + x4 + x3 + x2 + x + 1 == (x3 + x + 1)(x6 + x5 + x3 + x2 + 1).Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2)Производя далее попытки деления 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.143 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -2)Производя далее попытки деления 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.143 / 432Прикладная алгебраПоля ГалуаЗадачи143 / 432Решение (продолжение -2)Производя далее попытки деления 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).Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-23)Найти минимальное поле характеристики 3, в котороммногочлен f (x) = x3 + x + 2 ∈ F3 [x] раскладывается налинейные множители.В данном поле найти все корни данного многочлена.144 / 432Прикладная алгебраПоля ГалуаЗадачиЗадача (ПГ-23)Найти минимальное поле характеристики 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).144 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -1)2. Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:145 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -1)2.
Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:в поле своего расширения F = Fp [x]/(g(x))раскладывается на n линейных множителей —2n−1g(x) = (x − α) · (x − αp ) · (x − αp ) · . . . · (x − αp ),где α – произвольный корень g(x) в F ;не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.145 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -1)2.
Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:в поле своего расширения F = Fp [x]/(g(x))раскладывается на n линейных множителей —2n−1g(x) = (x − α) · (x − αp ) · (x − αp ) · . . . · (x − αp ),где α – произвольный корень g(x) в F ;не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.3. Рассмотрим поле F3 [x]/(g(x)) расширения многочленаg(x) = x2 + 2x + 2.145 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -1)2. Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:в поле своего расширения F = Fp [x]/(g(x))раскладывается на n линейных множителей —2n−1g(x) = (x − α) · (x − αp ) · (x − αp ) · . . .
· (x − αp ),где α – произвольный корень g(x) в F ;не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.3. Рассмотрим поле F3 [x]/(g(x)) расширения многочленаg(x) = x2 + 2x + 2. В этом поле если α — корень g(x), тоα2 = −2α − 2 = α + 1;145 / 432Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -1)2. Известно, что если g(x) — неприводимый многочлен степениn над конечным полем Fp , то он:в поле своего расширения F = Fp [x]/(g(x))раскладывается на n линейных множителей —2n−1g(x) = (x − α) · (x − αp ) · (x − αp ) · . . . · (x − αp ),где α – произвольный корень g(x) в F ;не имеет корней ни в каком конечном поле, содержащимменее, чем pn элементов.3. Рассмотрим поле F3 [x]/(g(x)) расширения многочленаg(x) = x2 + 2x + 2.
В этом поле если α — корень g(x), тоα2 = −2α − 2 = α + 1;α3 = α(α + 1) = α2 + α = 2α + 1 — тоже корень g(x)145 / 432Прикладная алгебраПоля ГалуаЗадачи146 / 432Решение (продолжение -2;α2 = α + 1)Действительно (подчёркиваем слагаемые, дающие в сумме 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.Прикладная алгебраПоля ГалуаЗадачи146 / 432Решение (продолжение -2;α2 = α + 1)Действительно (подчёркиваем слагаемые, дающие в сумме 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).Прикладная алгебраПоля ГалуаЗадачиРешение (продолжение -3)4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
