Лекции по прикладной алгебре. v2.0 (1127112), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

Убеждаемся, что (x − a) | (xp − x), где a ∈ Fp : при a = 0это очевидно, а в остальных случаях доказано, что a —корень многочлена xp−1 − 1 = (xp − x)/x.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем66 / 432Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены 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).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем67 / 432Многочлены над конечным полем...Используя доказанную теорему, завершим разложениеx15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1)на неприводимые надF2 многочлены.(∗)Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем67 / 432Многочлены над конечным полем...Используя доказанную теорему, завершим разложениеx15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1)на неприводимые над1(∗)F2 многочлены.4x(x15 + 1) = x16 + x = x2 + x, откуда все неприводимыемногочлены 4-й степени будут делителями x16 + x и,следовательно, x15 + 1. Таких многочленов 3: x4 + x + 1,x4 + x3 + 1 и x4 + x3 + x2 + x + 1, и их произведение даствторой сомножитель в (∗).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем67 / 432Многочлены над конечным полем...Используя доказанную теорему, завершим разложениеx15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1)на неприводимые над12(∗)F2 многочлены.4x(x15 + 1) = x16 + x = x2 + x, откуда все неприводимыемногочлены 4-й степени будут делителями x16 + x и,следовательно, x15 + 1.

Таких многочленов 3: x4 + x + 1,x4 + x3 + 1 и x4 + x3 + x2 + x + 1, и их произведение даствторой сомножитель в (∗).2x(x3 + 1) = x4 + x = x2 + x, откуда все неприводимыемногочлены 2-й степени будут делителями x4 + x и,следовательно, x3 + 1. Такой многочлен только один:x2 + x + 1 и x3 + 1 = (x + 1)(x2 + x + 1).В итоге получимx15 +1 = (x+1)(x4 +x+1)(x4 +x3 +1)(x4 +x3 +x2 +x+1)(x2 +x+1).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем68 / 432Многочлены над конечным полем...ТеоремаЛюбой неприводимый делитель многочлена xpстепень, не превосходящую n.n −1− 1 имеетПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем68 / 432Многочлены над конечным полем...ТеоремаЛюбой неприводимый делитель многочлена xpстепень, не превосходящую n.n −1− 1 имеетДоказательствоnПусть ϕ — неприводимый делитель xp − x степени k.defТогда F = Fp /(ϕ) — поле, котороеn рассмотрим oкак векторноепространство надFp с базисом1, x, . .

. , xk−1 .Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем69 / 432Многочлены над конечным полем....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.70 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...УтверждениеПусть β ∈ 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, что противоречит доказанномуранее.70 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...Следующая теорема нужна для того, чтобы раскладыватьмногочлены на множители.ТеоремаПусть β ∈ Fnp — корень неприводимого многочлена ϕ(x)n−1степени n с коэффициентами из Fp .

Тогда β, β p , . . . , β p :12все различны;исчерпывают список корней ϕ(x).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательнов степень p.71 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем...Следующая теорема нужна для того, чтобы раскладыватьмногочлены на множители.ТеоремаПусть β ∈ Fnp — корень неприводимого многочлена ϕ(x)n−1степени n с коэффициентами из Fp . Тогда β, β p , . .

. , β p :12все различны;исчерпывают список корней ϕ(x).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательнов степень p.Доказательство(1) Покажем, что если β — корень ϕ(x), то β p — тоже корень.71 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем72 / 432Многочлены над конечным полем...Поскольку ap = a для всех a ∈ Fp , то справедливоa0 + a1 x + .

. . + ak xkp= ap0 + ap1 xp + ap2 x2p + . . . + apk xkp == a0 + a1 (xp ) + a2 (xp )2 + . . . + ak (xp )k ,т.е. для любого многочлена f (x) ∈ Fp [x] выполняется равенствоp(∗)f (x) = f (xp ).Отсюда:ϕ(β) = 0 ⇔ ϕ(β)p = 0 ⇔ ϕ(β p ) = 0и β, β p , . . . , β pn−1— корни многочлена ϕ(x).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем73 / 432Многочлены над конечным полем...n−1(2) Осталось доказать, что все β, β p , . .

. , β pразличны, итогда (поскольку многочлен степени n имеет не более n корней)можно утверждать, что найдены все корни многочлена ϕ(x).lkПредположим, что β p = β p и без ограничения общностиl < k. Имеем:12nβ p = β;посколькуnk ·pn−kβp = βp=kβppn−kто β — корень уравнения x=pn−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 .74 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над F2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении F42 .Один корень получаем немедленно: x.74 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над F2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении F42 .Один корень получаем немедленно: x.По только что доказанной теореме можно выписать остальные:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x .74 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: решение уравненийПримерРассмотрим неприводимый над F2 многочлен f (x) = x4 + x3 + 1и найдем его корни в расширении F42 .Один корень получаем немедленно: x.По только что доказанной теореме можно выписать остальные:x2 , x4 = x3 + 1, x8 = x6 + 1 = x3 + x2 + x .Покажем, что, например, x2 действительно корень f (x):x4 + x3 + 1x 7→ x2 = x4·2 + x4+2 + 1x4 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.74 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + .

. . + an xn = 0,a0 , a1 , . . . , an ∈ Fp .Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнениеf (x) = a0 + a1 x + . . . + an xn = 0,a0 , a1 , . . . , an ∈ Fp .Если f (x) —неприводимый многочлен, то строим полекотором корнями f (x) будутx, xp , . . .

, xpn−1 ;Fp [x]/(f ), вПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнение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), полученныекорни объединяем.Одновременно строится минимальное поле характеристикиp, в котором данный многочлен f (x) раскладывается налинейные множители.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем75 / 432Как решать уравнения, когда корней нет?Пусть надо решить уравнение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), полученныекорни объединяем.Одновременно строится минимальное поле характеристикиp, в котором данный многочлен f (x) раскладывается налинейные множители.В конце данного раздела будет дан алгоритм нахождения всехкорней многочлена f (x) над полем Галуа Fp для общего случая.Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.

Коды ХэммингаГрупповые (линейные) коды76 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств77 / 432Прикладная алгебраПоля ГалуаСуществование и единственность поля Галуа из pn элементовРаздел IIIОсновные понятия теории ч.у.

Характеристики

Список файлов лекций