AA3-1(GF-I) (1127138), страница 7
Текст из файла (страница 7)
IКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Следствие (теорема Ферма)Все элементы поля Fnp , не исключая нуля, являются корнямиnмногочлена xp − x.ДоказательствоВынесем x за скобку:nxp − x = x xpn −1−1 .У второго сомножителя корнями будут все ненулевыеэлементы, а у первого — 0.55 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем: свойства...ТеоремаВ кольце многочленов над конечным полем..(xn − 1) .. (xm − 1) ⇔ n .. m.56 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем: свойства...ТеоремаВ кольце многочленов над конечным полем..(xn − 1) .. (xm − 1) ⇔ n .. m.ДоказательствоПусть n = mk. Сделаем замену xm = y, тогдаxn − 1 = y k − 1 и xm − 1 = y − 1. Делимость очевидна.56 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IКорни многочленов над конечным полемМногочлены над конечным полем: свойства...ТеоремаВ кольце многочленов над конечным полем..(xn − 1) .. (xm − 1) ⇔ n .. m.ДоказательствоПусть n = mk. Сделаем замену xm = y, тогдаxn − 1 = y k − 1 и xm − 1 = y − 1. Делимость очевидна..Предположим, что n 6 ..
m, т.е. n = km + r, 0 < r < m,тогдаxn − 1 =xr (xmk − 1)(xm − 1)+ xr − 1 =xm − 1xr (xmk − 1) m=(x − 1) + xr − 1.xm − 156 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Последнее выражение задает результат деления xn − 1 наxm − 1 с остатком, поскольку xmk − 1 делится на xm − 1 подоказанному выше.Остаток xr − 1 6= 0 в силу сделанных предположений.∴ xn − 1 не делится на xm − 1.57 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Последнее выражение задает результат деления xn − 1 наxm − 1 с остатком, поскольку xmk − 1 делится на xm − 1 подоказанному выше.Остаток xr − 1 6= 0 в силу сделанных предположений.∴ xn − 1 не делится на xm − 1.Теорема даёт возможность раскладывать многочлены xn − 1при составных n.Например, разложим x15 + 1 в F2 [x] (где −1 = +1):x15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1) ,x15 + 1 = (x5 + 1)(x10 + x5 + 1) .Возможность раскладывать многочлены специального вида нанеприводимые даёт следующая теорема.57 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем58 / 71Разложение многочленов на неприводимыеТеоремаВсе неприводимые многочлены n-й степени изnмногочлен xp − x.Fp [x]делятПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем58 / 71Разложение многочленов на неприводимыеТеоремаВсе неприводимые многочлены n-й степени изnмногочлен xp − x.Fp [x]делятДоказательствоn = 1. Убеждаемся, что (x − a) | (xp − x), где a ∈ Fp : при a = 0это очевидно, а в остальных случаях доказано, что a —корень многочлена xp−1 − 1 = (xp − x)/x.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем58 / 71Разложение многочленов на неприводимыеТеоремаВсе неприводимые многочлены 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).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем59 / 71Пример: разложение x15 + 1 ∈ F2 [x]Проверяем степени 2 :24 − 1 = 15|15, 23 − 1 = 7 6 |15, 22 − 1 = 3|15, 21 − 1 = 1|15,1234x(x15 + 1) = x2 + x, откуда все неприводимые многочлены4-й степени будут делителями x16 + x и, следовательно,x15 + 1. Таких многочленов 3:x4 + x + 1, x4 + x3 + 1 и x4 + x3 + x2 + x + 1.2x(x3 + 1) = x2 + x, откуда все неприводимые многочлены 2-йстепени будут делителями x4 + x и, следовательно, x3 + 1.Такой многочлен только один: x2 + x + 1.1x(x1 + 1) = x2 + x, откуда (тривиально) единственныйнеприводимый многочлен 1-й степени x + 1 делит x2 + x.Итого: разложение x15 − 1 на неразложимые надx15 +1=F2 многочлены —24434(x+1)(x +x+1)(x +x+1)(x +x +1)(x +x3 +x2 +x+1).ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем60 / 71Многочлены над конечным полем...ТеоремаЛюбой неприводимый многочлен-делитель xpстепень, не превосходящую n.nn −1− 1 имеетЕсли делящий xp −1 − 1 неприводимый многочлен имеетстепень равную n, то он называется примитивныммногочленом.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем60 / 71Многочлены над конечным полем...ТеоремаЛюбой неприводимый многочлен-делитель xpстепень, не превосходящую n.n −1− 1 имеетnЕсли делящий xp −1 − 1 неприводимый многочлен имеетстепень равную n, то он называется примитивныммногочленом.ДоказательствоnПусть ϕ — неприводимый делитель xp − x степени k.defТогда F = Fp /(ϕ) — поле, котороеn рассмотрим какo векторноепространство надFpс базисом1, x, . .
. , xk−1 .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем61 / 71Многочлены над конечным полем....nОбозначим x = α. Поскольку (xp − x) ..ϕ, то в F имеемnαp − α = 0.k−1PЛюбой элемент F выражается через базис: β =ai α i .i=0Возведя обе части этого равенства в степень pn , получимpnk−1k−1PPnipai αi = β,β =ai α=i=0i=0т.е. β — корень уравненияnxp − x = 0 .(∗)Итак, каждый элемент поля F является корнем (∗), но у (∗) неболее pn различных корней, а |F | = pk ∴ n > k.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IКорни многочленов над конечным полемМногочлены над конечным полем...УтверждениеПусть β ∈ Fnp имеет порядок l, а его м.м. m(x) имеет степень k...Тогда ¶ (pk − 1) .. l, а если r < k, то · (pr − 1) 6 .. l.62 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем...УтверждениеПусть β ∈ Fnp имеет порядок l, а его м.м. m(x) имеет степень k...Тогда ¶ (pk − 1) ..
l, а если r < k, то · (pr − 1) 6 .. l.Доказательство¶ По неприводимому многочлену k-й степени m(x) строимполе из pk элементов. Все его ненулевые элементы, в томkчисле и β, являются корнями уравнения xp −1 − 1 = 0, т.е.kkβ p −1 − 1 = 0 и β p −1 = 1, но deg β = l ⇒ l | (pk − 1)..· Пусть (pr − 1) .. l и r < k. Тогда β — корень уравнения.rrxp − 1 = 0, а т.к.
m(x) — м.м. для β, то (xp − 1)..m(x) (былоrдоказано) ⇒ найден неприводимый делитель xp − 1 степениk, но k > r ⇒ противоречие доказанному ранее.62 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем...Следующая теорема позволяет раскладывать многочлены намножители.Теорема (свойство корней неприводимого многочлена)Пусть β — корень неприводимого многочлена f (x) степени n с2n−1коэффициентами из Fp . Тогда элементы β, β p , β p , .
. . , β p :¶ все различны; · исчерпывают список всех n корней f (x)(их называют смежными).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательно встепень p.63 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем...Следующая теорема позволяет раскладывать многочлены намножители.Теорема (свойство корней неприводимого многочлена)Пусть β — корень неприводимого многочлена f (x) степени n с2n−1коэффициентами из Fp . Тогда элементы β, β p , β p , .
. . , β p :¶ все различны; · исчерпывают список всех n корней f (x)(их называют смежными).Т.е. чтобы получить все корни неприводимого многочлена,достаточно найти один из них и возводить его последовательно встепень p.Доказательство¶ Покажем, что если β — корень f (x), то β p — тоже корень.63 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем...Поскольку 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 ,т.е. для любого многочлена ϕ(x) ∈ Fp [x] выполняется равенствоp(∗)ϕ(x) = ϕ(xp ).Отсюда:f (β) = 0 ⇔ f (β)p = 0 ⇔ f (β p ) = 0и β, β p , . . . , β pn−1— корни многочлена f (x).64 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем65 / 71Многочлены над конечным полем...n−1· Осталось доказать, что все β, β p , . .
. , β pразличны, итогда (многочлен степени n имеет не более n корней) можноутверждать, что найдены все корни многочлена f (x).lkПредположим, что β p = β p и без ограничения общностиl < k. Имеем:n1β p = β;2поскольку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 — противоречие.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем66 / 71Многочлены над конечным полем: решение уравненийПримерЗадача. Найти корни неприводимого надf (x) = x4 + x3 + 1F2многочленаПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем66 / 71Многочлены над конечным полем: решение уравненийПримерЗадача. Найти корни неприводимого надF2многочленаf (x) = x4 + x3 + 1Решение. Один корень получаем немедленно: x (или x).ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем66 / 71Многочлены над конечным полем: решение уравненийПримерЗадача. Найти корни неприводимого надF2многочленаf (x) = x4 + x3 + 1Решение. Один корень получаем немедленно: x (или x).По только что доказанной теореме можно выписать остальные:x2 ,x4 = x3 + 1,x8 = x6 + 1 = x3 + x2 + x.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полем66 / 71Многочлены над конечным полем: решение уравненийПримерЗадача.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
