Лекции по прикладной алгебре. v1.1 (1127111), страница 6
Текст из файла (страница 6)
Убеждаемся, что (x − a) | (xp − x), где a ∈ Fp : при a = 0это очевидно, а в остальных случаях доказано, что a —корень многочлена xp−1 − 1 = (xp − x)/x.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем60 / 160Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xp − x.Fp [x] являютсяДоказательствоn = 1. Убеждаемся, что (x − a) | (xp − x), где a ∈ Fp : при a = 0это очевидно, а в остальных случаях доказано, что a —корень многочлена xp−1 − 1 = (xp − x)/x.n > 1. Строим по неприводимому и (без ограничения общности —нормированному) многочлену f (x) степени n поле Fnp .nВ этом поле x — корень и f (x), и xp −1 − 1, причёмf (x) — м.м.
для него.nПо свойствам м.м., xp −1 − 1 делится на f (x).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...Используя эту теорему, мы можем завершить разложение:x15 +1 = (x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1)(x2 +x+1)— берём над F2 все три неприводимых многочлены 4-й степени4(x(x15 + 1) = x2 + x) и единственный неприводимый многочлен22-й степени (x(x3 + 1) = x2 + x).61 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем61 / 160Многочлены над конечным полем...Используя эту теорему, мы можем завершить разложение:x15 +1 = (x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1)(x2 +x+1)— берём над F2 все три неприводимых многочлены 4-й степени4(x(x15 + 1) = x2 + x) и единственный неприводимый многочлен22-й степени (x(x3 + 1) = x2 + x).ТеоремаЛюбой неприводимый делитель многочлена xpстепень, не превосходящую n.n −1− 1 имеетПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем61 / 160Многочлены над конечным полем...Используя эту теорему, мы можем завершить разложение:x15 +1 = (x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1)(x2 +x+1)— берём над F2 все три неприводимых многочлены 4-й степени4(x(x15 + 1) = x2 + x) и единственный неприводимый многочлен22-й степени (x(x3 + 1) = x2 + x).ТеоремаЛюбой неприводимый делитель многочлена xpстепень, не превосходящую n.n −1− 1 имеетДоказательствоnПусть ϕ — неприводимый делитель xp − x степени k.defТогда F = Fp /(ϕ) — поле, котороеn рассмотрим oкак векторноепространство надFp с базисом1, x, .
. . , xk−1 .Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем62 / 160Многочлены над конечным полем....nОбозначим x = α. Поскольку (xp − x) ..ϕ, то в F имеемnαp − α = 0.k−1PЛюбой элемент F выражается через базис: β =ai αi .i=0Возведя обе части этого равенства в степень pn , получимpnk−1k−1PPnip=ai αi = β,ai αβ =i=0i=0т.е. β — корень уравненияnxp − x = 0 .(∗)Итак, каждый элемент поля F является корнем (∗), но у (∗) неболее pn различных корней, а |F | = pk .∴ n > k.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...УтверждениеПусть β ∈ Fnp имеет порядок l, а его м.м. m(x) имеет степень k...Тогда (a) (pk − 1) .. l, а если r < k, то (b) (pr − 1) 6 ..
l.63 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...УтверждениеПусть β ∈ Fnp имеет порядок l, а его м.м. m(x) имеет степень k...Тогда (a) (pk − 1) .. l, а если r < k, то (b) (pr − 1) 6 ..
l.Доказательствоa) По неприводимому многочлену k-й степени m(x) строимполе из pk элементов. Все его ненулевые элементы, в том числеkи β, являются корнями уравнения xp −1 − 1 = 0, т.е.kkβ p −1 − 1 = 0 и β p −1 = 1, но deg β = l ⇒ l | (pk − 1)..b) Пусть (pr − 1) .. l и r < k. Тогда β — корень уравнения.rrxp − 1 = 0, а т.к.
m(x) — м.м. для β, то (xp − 1)..m(x) (былодоказано). Мы нашли неприводимый делитель многочленаrxp − 1 степени k, но k > r, что противоречит доказанномуранее.63 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...Следующая теорема нужна для того, чтобы раскладыватьмногочлены на множители.ТеоремаПусть β ∈ Fnp — корень неприводимого многочлена ϕ(x)n−1степени n с коэффициентами из Fp . Тогда β, β p , . . . , β p :12все различны;исчерпывают список корней ϕ(x).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательнов степень p.64 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...Следующая теорема нужна для того, чтобы раскладыватьмногочлены на множители.ТеоремаПусть β ∈ Fnp — корень неприводимого многочлена ϕ(x)n−1степени n с коэффициентами из Fp . Тогда β, β p , .
. . , β p :12все различны;исчерпывают список корней ϕ(x).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательнов степень p.Доказательство(1) Покажем, что если β — корень ϕ(x), то β p — тоже корень.64 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем65 / 160Многочлены над конечным полем...Поскольку ap = a для всех a ∈ Fp , то справедливо(a0 + a1 x + .
. . + ak xk )p = ap0 + ap1 xp + ap2 x2p + . . . + apk xkp == a0 + a1 (xp ) + a2 (xp )2 + . . . + ak (xp )k ,т.е. для любого многочлена f (x) ∈ Fp [x] выполняется равенство(f (x))p = f (xp ) .Отсюда:ϕ(β) = 0 ⇔ ϕ(β)p = 0 ⇔ ϕ(β p ) = 0и β, β p , . . . , β pn−1— корни многочлена ϕ(x).(∗)Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем66 / 160Многочлены над конечным полем...n−1(2) Осталось доказать, что все β, β p , . .
. , β pразличны, итогда (поскольку многочлен степени n имеет не более n корней)можно утверждать, что найдены все корни многочлена ϕ(x).lkПредположим, что β p = β p и без ограничения общностиl < k. Имеем:12nβ p = β;посколькуnk ·pn−kβp = βp=kβppn−kто β — корень уравнения xp=n−k+l −1βplpn−kn−k+l= βp,− 1 = 0.Из теоремы «Все неприводимые многочлены n-й степени надFp являются делителями xpn − x» получаемn − k + l > n ⇒ l > k — противоречие.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над F2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении F42 .67 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над F2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении F42 .Один корень получаем немедленно: x.67 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над F2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении F42 .Один корень получаем немедленно: x.По только что доказанной теореме можно выписать остальные:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x .67 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над F2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении F42 .Один корень получаем немедленно: x.По только что доказанной теореме можно выписать остальные:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x .Покажем, что, например, x2 действительно корень f (x):x4 + x3 + 1 |x7→x2 = x4·2 + x4+2 + 1 |x4 7→x3 +1 == (x3 + 1)2 + (x3 + 1)x2 + 1 = (x6 + 6 1) + x5 + x2 + 6 1 == x6 + x5 + x2 = x2 (x4 + x3 + 1) = x2 · 0 = 0.67 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем68 / 160Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + .
. . + an xn = 0,a0 , a1 , . . . , an ∈ Fp .Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем68 / 160Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + . . . + an xn = 0,a0 , a1 , . . . , an ∈ Fp .Если f (x) —- неприводимый многочлен, то строим полекотором корнями f (x) будутx, xp , . . . , xpn−1 ;Fp [x]/(f ), вПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем68 / 160Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + .
. . + an xn = 0,a0 , a1 , . . . , an ∈ Fp .Если f (x) —- неприводимый многочлен, то строим полекотором корнями f (x) будутx, xp , . . . , xpn−1 ;Fp [x]/(f ), в- имеет делители, то раскладываем f (x) на неприводимыемножители и находим их корни как в п. 1), полученныекорни объединяем.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды69 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел IIКоды БЧХЧто надо знать70 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа расширения поляПример (полеF42 )Поле F42 можно строить с помощью любого из трехнеприводимых многочленов (но пока не доказано):x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Удобнее всего это сделать, если взять многочленf (x) = x4 + x + 1 (почему?).71 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа расширения поляПример (полеF42 )Поле F42 можно строить с помощью любого из трехнеприводимых многочленов (но пока не доказано):x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Удобнее всего это сделать, если взять многочленf (x) = x4 + x + 1 (почему?).Будем задавать элементы F42 наборами коэффициентовмногочлена-остатка при делении на f , записывая их в порядкевозрастания степеней.Порождающим является элемент α = x, который записываетсякак (0, 1, 0, 0).Вычислим степени α, сведя результаты в таблицу.71 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовМультипликативная группа поляx4 = x + 172 / 160F42 ∼= F2 [x]/(x4 + x + 1)степень αα=α2 =α3 =1 + α = α4 =α + α2 = α5 =α2 + α3 = α6 =3α + α + 1 = α3 + α4 = α7 =1 + α2 = α + 1 + α2 + α = α8 =α + α3 = α9 =22α + 1 + α = α + α4 = α10 =α + α2 + α3 = α11 =231 + α + α + α = α2 + α3 + α4 = α12 =1 + α2 + α3 = α + α2 + α3 + α4 = α13 =1 + α3 = α + α3 + α4 = α14 =1 = α + α4 = α15 =1(0,(0,(0,(1,(0,(0,(1,(1,(0,(1,(0,(1,(1,(1,(1,x1,0,0,1,1,01,0,1,1,1,1,0,0,0,x20,1,0,0,1,1,01,0,1,1,1,1,0,0,x30)0)1)0)0)1)1)0)1)0)1)1)1)1)0)Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементов73 / 160Имея такую таблицу, очень просто производить умножение:(x3 + x + 1) · (x2 + x + 1) = x2— как получить этобез перемножения?(1, 1, 0, 1) · (1, 1, 1, 0) =?— то же в векторной форме...α= xα7 α10 = α17 = α2— по векторной формевзять из таблицы!.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m — максимальный порядок элемента в конечнойабелевой группе G.Тогда порядок любого элемента x ∈ G = h G, ◦, e i делит m.74 / 160Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовПорядок элемента конечной группыЛемма (о порядке элемента конечной группы)Пусть m — максимальный порядок элемента в конечнойабелевой группе G.Тогда порядок любого элемента x ∈ G = h G, ◦, e i делит m.ДоказательствоГруппа G однозначно разлагается в прямую сумму циклическихгрупп, порядки которых являются степенями простых чисел.Для каждого простого делителя pi порядка группы найдемциклическую группу максимального порядка pki .Обозначим произведение чисел pki через M .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
