AA3-1(GF-II) (1127139), страница 2
Текст из файла (страница 2)
Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов18 / 78Важные замечания1. Существование неприводимых многочленовИз данной леммы следует неравенство ndn 6 pn . Простаяоценкаn−1XXpn − 1ndn = pn −kdk > pn −pk = pn −> 0.p−1k|n, k<nk=0доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый многочлен степени n.2. Среднее число неприводимых нормированных многочленовИз данной леммы вытекает, что при n → ∞ имеем dn ∼ pn /n.Т.е. неприводимые нормированные многочлены составляютприблизительно 1/n-ю часть всех многочленов степени n надполем Fp .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIСуществование и единственность поля Галуа из pn элементов19 / 78Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальный многочлен элемента α ∈ Fnp и d — еёстепень.Тогда поле Fp [x]/(m) изоморфно подполю Fdp , порожденномустепенями α.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов19 / 78Изоморфизм полей Галуа с одинаковым числом элементовДокажем вторую часть основной теоремы о конечных полях:любые два поля с одинаковым числом элементов изоморфны.ТеоремаПусть m — минимальный многочлен элемента α ∈ Fnp и d — еёстепень.Тогда поле Fp [x]/(m) изоморфно подполю Fdp , порожденномустепенями α.ДоказательствоСтепени α принадлежат d-мерному пространству с базисом1, α, α2 , .
. . , αd−1 , которое является подполем поля Fnp ,поскольку замкнуто относительно сложения и умножения исодержит 0 и 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать20 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваКольцоFp [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = Fp [x]/(f ) по модулю главного идеала (f ) возможноприводимого многочлена f ∈ Fp [x].Если f неприводим, то K(p, f ) — поле и этот случай ужерассмотрен.21 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваКольцо21 / 78Fp [x]/(f )В приложениях часто используется кольцо многочленовK(p, f ) = Fp [x]/(f ) по модулю главного идеала (f ) возможноприводимого многочлена f ∈ Fp [x].Если f неприводим, то K(p, f ) — поле и этот случай ужерассмотрен.В любом случае K(p, f ) — векторное пространство надсовокупность многочленов степени меньшей deg f .Fp т.е.Fp [x] = { 0, 1, . .
. , p − 1, x, x + 1, . . . , f , . . . };(f ) = f = { t · f } , t ∈ Fp [x];Fp [x]/(f ) = f , g, h, . . . , deg f, deg g, . . . 6 deg f − 1;g = { t · f + g };h = { t · f + h };...g + f = g,g · f = f.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространства22 / 78Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f . Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).def2ϕ — единственный в Iϕ нормированный многочленминимальной степени.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространства22 / 78Нормированный делитель порождающего элемента идеалаТеоремаПусть ϕ — неприводимый нормированный многочлен, которыйделит f .
Тогда1совокупность всех вычетов, кратных ϕ, образует идеал вкольце классов вычетов по модулю f :Iϕ = { t · ϕ } C Fp [x]/(f ).def2ϕ — единственный в Iϕ нормированный многочленминимальной степени.Доказательствоu, v, ϕ ∈ Fp [x],k = deg ϕ 6 deg fϕ = a0 + a1 x + . . . + ak−1 xk−1 + xk ,f = ψϕ.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространства23 / 78Нормированный делитель...1. Проверим, что Iϕ — идеал в кольцеFp [x]/(f ).1g ∈ Iϕh ∈ Fp [x]/(f ), h ⊆ g⇔g = uϕh = vg = vuϕ⇒ h ∈ Iϕ .2g, h ∈ Iϕ ⇔g = uϕh = vϕ⇒ g + h = (u + v)ϕ ∈ Iϕ .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЦиклические подпространстваНормированный делитель...2. Покажем, что в Iϕ нет других, кромеϕ = a0 + a1 x + . . . + ak−1 xk−1 + xkнормированных многочленов степени, меньшей k = deg ϕ.Пустьg = b0 + b1 x + . . . + xm .Тогда:g ∈ Iϕ ⇔ g = uϕ ⇒ deg g = m > deg ϕ = k.24 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространства25 / 78Подыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЦиклические подпространства25 / 78Подыдеал как векторное пространствоТеоремаПусть ϕ — неприводимый нормированный делительмногочлена f ∈ Fp [x] отличный от f , deg f = n, deg ϕ = k.Тогда идеал (ϕ) — векторное пространство размерности n − k.ДоказательствоБез доказательства.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваЦиклическое пространство: определениеПусть V — n-мерное векторное пространство наднекоторым полем F .Фиксируем некоторый базис V .Тогда V ∼= Fn == { ( a0 , .
. . , an−1 ) | ai ∈ F, i = 0, 1, . . . , n − 1 } —координатное пространство.ОпределениеПодпространство координатного пространства F n называетсяциклическим, если вместе с набором (a0 , . . . , an−1 ) оносодержит циклический сдвиг (вправо) этого набора, т.е. набор(an−1 , a0 , . . . , an−2 ) (а следовательно и все циклическиесдвиги на произвольное число позиций влево и вправо).26 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространства27 / 78Кольцо классов вычетов по модулю многочлена xn − 1Fp [x]/(xn − 1), рассматриваемом nкак векторное oпространство над полем Fp имеется базис 1, x, . . . , xn−1 .В кольцеЦиклический сдвиг координат в этом базисе равносиленумножению на x:(a0 + a1 x + . . . + an−2 xn−2 + an−1 xn−1 ) · x == (a0 x + a1 x2 + . .
. + an−2 xn−1 + an−1 xn ) == (an−1 + a0 x + a1 x2 + . . . + an−2 xn−1 ),т.к. в этом кольце xn = 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваИдеал вFp [x]/(xn − 1) — циклическое пространствоТеоремаПусть I — подпространство кольца Fp [x]/(xn − 1).Тогда I — циклическое ⇔ I C Fp /(xn − 1).28 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваИдеал вFp [x]/(xn − 1) — циклическое пространствоТеоремаПусть I — подпространство кольца Fp [x]/(xn − 1).Тогда I — циклическое ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг ⇒ I — циклическое.28 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваИдеал вFp [x]/(xn − 1) — циклическое пространствоТеоремаПусть I — подпространство кольца Fp [x]/(xn − 1).Тогда I — циклическое ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг ⇒ I — циклическое.Пусть I — циклическое подпространство кольцаFp /(xn − 1) и g ∈ I.Тогда g · x, g · x2 , . . .
— циклические сдвиги, т.е. такжепринадлежат I.Значит, g · f ∈ I для любого многочлена f , поэтому I —идеал.28 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваПримитивные корниБыло показано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором полеFq = Fnp характеристики p.Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1.29 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространства29 / 78Примитивные корниБыло показано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором полеFq = Fnp характеристики p.Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1.
Справедливо:В Fq выполняется равенство xkp − 1 = (xk − 1)p , поэтомуинтересен случай, когда n взаимно просто с p: тогда умногочлена xn − 1 кратных корней нет (он взаимно простсо своей производной nxn−1 ).Равенство xn = 1 означает, что порядок элемента xв мультипликативной циклической группе F∗q делит n.Вывод: корни уравнения xn − 1 = 0 образуют группу корнейстепени n из единицы — подгруппу в F∗q .Эта подгруппа также циклическая; её порождающие элементыназываются примитивными корнями степени n.ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
