AA3-1(GF-I) (1127138), страница 6
Текст из файла (страница 6)
Любой элемент Fnp представим в виде линейной комбинацииуказанных векторов:a0 + a1 x + . . . + an−1 xn−1 } == a0 {1} + a1 {x} + . . . + an−1 {xn−1 .2. Обратно, пусть g(x) = b0 {1} + b1 {x} + . . . + bn−1 {xn−1 } = 0.Это означает, что многочлен g(x) степени n − 1 делится нанекоторый многочлен n-й степени, что возможно лишь приb0 = b1 = .
. . = bn−1 = 0, т.е. система {1}, {x}, . . . , {xn−1 }линейно независима.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемC — расширение поля RЗамечание. Построение поля с помощью вычетов по модулюнекоторого неприводимого многочлена и аналоги доказанныхтеорем справедливы не только в случае конечных полей.45 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полем45 / 71C — расширение поля RЗамечание. Построение поля с помощью вычетов по модулюнекоторого неприводимого многочлена и аналоги доказанныхтеорем справедливы не только в случае конечных полей.Например:R1рассмотрим поле действительных чиселмногочленов R[x] над ним;2в3построим поле F как факторкольцо: F = R[x]/ x2 + 1 ;45R[x]и кольцовозьмём неприводимый многочлен x2 + 1;F также и векторное пространство над R; его базис —{ {1}, {x} } и каждый его элемент z ∈ F можно представитьв виде z = a{1} + b{x}, a, b ∈ R;поле F изоморфно полю комплексных чисел C = a + ib | a, b ∈ R, i2 = −1 ,изоморфизм задаётся соответствием {1} 7→ 1, {x} 7→ i.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемПодполя46 / 71FnpЛеммаЕсли полеFnpсодержит подполеFkp , тоk | n.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемПодполя46 / 71FnpЛеммаЕсли полеFnpсодержит подполеFkp , тоk | n.ДоказательствоЕсли поле k1 содержится в поле ( k1 ⊂ k2 ), то элементы k2можно умножать на элементы из k1 , а результаты складывать.Поэтому поле k2 является векторным пространством надполем k1 некоторой размерности d — значит, в нём |k1 |dэлементов.Для нашего случая: pn = (pk )d , что и означает k | n.Ясно, чтоFp — всегда подполе Fnp(случай k = 1).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать47 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМинимальный многочленРассмотрим поле Fnp , а в нём — какой-нибудь элемент β ибудем интересоваться многочленами, для которых этот элементявляется корнем.ОпределениеМногочлен mβ (x) называется минимальным (м.м.) илиминимальной функцией для β, если это нормированныймногочлен минимальной степени, из Fp [x] для которого βявляется корнем.Другими словами, должны выполняться три свойства:1mβ (β) = 0;2∀ f (x) ∈ Fp [x] : ( deg f (x) < deg mβ (x) ⇒ f (β) 6= 0 );3коэффициент при старшей степени в mβ (x) равен 1.48 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМинимальный многочлен из неприводимогоРассмотрим поле Fnp = Fp [x]/ (a(x)), порождаемоенеприводимым многочленом a(x) = a0 + a1 x + . . . + an xn иубедимся, что многочлен a−1n a(x) — минимальный дляэлемента x = ( 0, 1, 0, .
. . , 0 ) ∈ Fnp .49 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМинимальный многочлен из неприводимогоРассмотрим поле Fnp = Fp [x]/ (a(x)), порождаемоенеприводимым многочленом a(x) = a0 + a1 x + . . . + an xn иубедимся, что многочлен a−1n a(x) — минимальный дляэлемента x = ( 0, 1, 0, . . . , 0 ) ∈ Fnp .Действительно, с одной стороны —a0 1 + a1 x + . . . + an xn = a0 + a1 x + . . .
+ an xn = 0,т.е. x — корень a(x), а значит и a−1n a(x).С другой, пусть b(x) = b0 1 + b1 x + . . . + bn−1 xn−1 = 0.Но тогда b0 1 + b1 x + . . . + bn−1 xn−1n = 0, т.е. имеемo линейнуюn−1зависимость между элементами 1, x, . . . , x— базисаnполя Fp как векторного пространства над Fp , откудаb0 = b1 = . . . = bn−1 = 0.49 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМинимальный многочлен из неприводимогоРассмотрим поле Fnp = Fp [x]/ (a(x)), порождаемоенеприводимым многочленом a(x) = a0 + a1 x + . .
. + an xn иубедимся, что многочлен a−1n a(x) — минимальный дляэлемента x = ( 0, 1, 0, . . . , 0 ) ∈ Fnp .Действительно, с одной стороны —a0 1 + a1 x + . . . + an xn = a0 + a1 x + . . . + an xn = 0,т.е. x — корень a(x), а значит и a−1n a(x).С другой, пусть b(x) = b0 1 + b1 x + . . . + bn−1 xn−1 = 0.Но тогда b0 1 + b1 x + . .
. + bn−1 xn−1n = 0, т.е. имеемo линейнуюn−1зависимость между элементами 1, x, . . . , x— базисаnполя Fp как векторного пространства над Fp , откудаb0 = b1 = . . . = bn−1 = 0.x2 = x2 = (0, 0, 1, 0, . . . , 0),...,xn−1 = (0, . . . , 0, 1)49 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.50 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.ДоказательствоПусть mβ (x) — м.м. для β и mβ (x) = m1 (x)m2 (x).Тогдаm1 (β) = 0mβ (β) = 0 ⇒,m2 (β) = 0но deg m1 < deg m и deg m2 < deg m ⇒ β не может бытькорнем ни m1 (x), ни m2 (x).50 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеПусть в некотором поле Галуа mβ (x) — м.м. для элемента β, аf (x) — многочлен такой, что f (β) = 0.Тогда f (x) делится на mβ (x).51 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеПусть в некотором поле Галуа mβ (x) — м.м. для элемента β, аf (x) — многочлен такой, что f (β) = 0.Тогда f (x) делится на mβ (x).ДоказательствоРазделим f (x) на mβ (x) с остатком:f (x) = u(x)mβ (x) + v(x) ,deg v < deg m .Подставляя в это равенство β, получаем0 = f (β) = u(β) mβ (β) +v(β) = v(β) ,| {z }=0т.е. β — корень v(x), что противоречит минимальности mβ (x).51 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждого элемента поля существует не более одного м.м.52 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждого элемента поля существует не более одного м.м.ДоказательствоПусть минимальных многочленов два.Они взаимно делят друг друга, а значит, различаются наобратимый множитель-константу.Поскольку минимальный многочлен нормирован, эта константаравна 1, т.е.
данные многочлены совпадают.52 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеДля каждого элемента β поля Fnp существует (единственный)м.м. и его степень не превосходит n.53 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеДля каждого элемента β поля Fnp существует (единственный)м.м. и его степень не превосходит n.ДоказательствоРассмотрим следующие элементы поля Fnp : 1, β, β 2 , .
. . , β n —их n + 1 штука, а размерность Fnp как векторного пространстваравна n ⇒ эти элементы линейно зависимы, т.е. существуюттакие не все равные 0 коэффициенты c0 , . . . , cn , чтоc0 + c1 β + . . . + cn β n = 0,⇒ β — корень многочлена f (x) = c0 + c1 x + . . . + cn xn .Минимальным многочленом для β будет некоторыйнормированный неприводимый делитель f (x) (т.е. f (x) ∈ Fnp ).53 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IКорни многочленов над конечным полемМногочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поля Fnp является корнемnмногочлена xp −1 − 1, т.е.nxp −1 − 1 = (x − β1 ) · . . . · (x − βpn −1 ),nгде β1 , . . . , βpn −1 = Fn∗p = Fp r {0}.54 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поля Fnp является корнемnмногочлена xp −1 − 1, т.е.nxp −1 − 1 = (x − β1 ) · .
. . · (x − βpn −1 ),nгде β1 , . . . , βpn −1 = Fn∗p = Fp r {0}.ДоказательствоnFn∗p — циклическая группа по умножению порядка p − 1.n∗Порядок deg α любого элемента α ∈ Fp (т.е. порядокциклической подгруппы hαi) по теореме Лагранжа делитпорядок группы.Поэтому pn − 1 = q · deg α, αdeg α = 1 иαpn −1− 1 = αq deg α − 1 = (αdeg α )q − 1 = 1q − 1 = 0.54 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Следствие (теорема Ферма)Все элементы поля Fnp , не исключая нуля, являются корнямиnмногочлена xp − x.55 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
