Лекции по прикладной алгебре. v2.0 (1127112), страница 5
Текст из файла (страница 5)
. . , 1 + . . . + 1 } ⊆ k,Fp =Fp .то при умножении «числа» из поля Fp можнозаменять на соответствующие элементы из поля F ;аксиомы векторного пространства — выполняются в силусвойств арифметических операций в поле k.СледствиеКонечное поле (как векторное пространство) состоит из pnэлементов, p — простое, n — натуральное.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем49 / 432Поля Галуа как кольца вычетов или векторные пространстваПолеFnp есть конечная АС с элементами-многочленамиM =a0 + a1 x + . . .
+ an−1 xn−1⊂ Fp [x],которую можно рассматривать какфакторкольцо вычетов по модулю некоторогонеприводимого многочлена f (x) степени n над полемFnp ∼= Fp [x]/(f (x)); +p , ·pили какn-мерное координатное пространство над полемFnp ∼= M, Fp ; +p , ·p .Fp :Fp :Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемБазис в50 / 432FnpТеоремаЭлементы 1, x, . .
. , xn−1 образуют базисFnp .Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемБазис в50 / 432FnpТеоремаЭлементы 1, x, . . . , xn−1 образуют базисFnp .ДоказательствоЛюбой элемент Fnp представим в виде линейнойкомбинации указанных векторов:a0 + a1 x + . . . + an−1 xn−1 = a0 1 + a1 x + . . .
+ an−1 xn−1 .Обратно, пусть g(x) = b0 1 + b1 x + . . . + bn−1 xn−1 = 0.Это означает, что многочлен g(x) степени n − 1 делится нанекоторый многочлен n-й степени, что возможнолишь приnob0 = b1 = . . . = bn−1 = 0, т.е. система 1, x, . . . , xn−1линейно независима.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРасширение поляRЗамечаниеПостроение поля с помощью вычетов по модулю некоторогонеприводимого многочлена и аналоги доказанных теоремсправедливы не только в случае конечных полей.51 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРасширение поляRЗамечаниеПостроение поля с помощью вычетов по модулю некоторогонеприводимого многочлена и аналоги доказанных теоремсправедливы не только в случае конечных полей.Например:12345рассмотрим поле действительных чисел R и кольцомногочленов R[x] над ним;в R[x] возьмём неприводимый многочлен x2 + 1;построим поле F как факторкольцо: F = R[x]/(x2 + 1);F также и векторное пространство над R; его базис — 1, xи каждый его элемент z ∈ F можно представить в видеz = a1 + bx, a, b ∈ R;Поле F изоморфно полю комплексныхчиселC = a + ib | a, b ∈ R, i2 = −1 : изоморфизм задаётсясоответствием 1 7→ 1, x 7→ i.51 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемПодполя52 / 432FnpЛеммаЕсли полеFnp содержит подполе Fkp , тоk | n.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемПодполя52 / 432FnpЛеммаЕсли полеFnp содержит подполе Fkp , тоk | n.ДоказательствоЕсли поле k1 содержится в поле k1 ⊂ k2 , то элементы k2можно умножать на элементы из k1 , а результаты складывать.Поэтому поле k2 является векторным пространством над полемk1 некоторой размерности d — значит, в нём |k1 |d элементов.Для нашего случая: pn = (pk )d , что и означает k | n.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды53 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств54 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать55 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМинимальный многочленРассмотрим поле Fnp , а в нём — какой-нибудь элемент β ибудем интересоваться многочленами, для которых этот элементявляется корнем.ОпределениеМногочлен m(x) называется минимальной функцией (илиминимальным многочленом, м.м.) для β, если m(x) —нормированный многочлен минимальной степени, для которогоβ является корнем.Другими словами, должны выполняться три свойства:123m(β) = 0;∀f (x) ∈ Fp [x] : (deg f (x) < deg m(x) ⇒ f (β) 6= 0);коэффициент при старшей степени в m(x) равен 1.56 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМинимальные многочлены: пример построенияРассмотрим Fnp = Fp [x]/(a(x)), гдеa(x) = a0 + a1 x + .
. . + an xn — неприводимый многочлен.Тогда для элемента x ∈ Fnp многочлен a−1n a(x) —минимальный.57 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем57 / 432Минимальные многочлены: пример построенияРассмотрим Fnp = Fp [x]/(a(x)), гдеa(x) = a0 + a1 x + . . . + an xn — неприводимый многочлен.Тогда для элемента x ∈ Fnp многочлен a−1n a(x) —минимальный.12a0 1 + a1 x + . . . + an xn = a0 + a1 x + . . . + an xn ≡p 0,т.е.
x — корень a(x), но тогда x — корень и a−1n a(x).Пусть существует многочлен b0 + b1 x + . . . + bn−1 xn−1 , длякоторогоb0 1+b1 x+. . .+bn−1 xn−1 = b0 1+b1 x+. . .+bn−1 xn−1 = 0.Это равенство задает линейную зависимость междуклассами 1, x, . . . , xn−1 , которые образуют базис полякак векторного пространства над Fp .Поэтому b0 = b1 = .
. . = bn−1 = 0.FnpПрикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.58 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.ДоказательствоПусть 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).58 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеПусть в некотором поле Галуа m(x) — м.м. для элемента β, аf (x) — многочлен такой, что f (β) = 0.Тогда f (x) делится на m(x).59 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем59 / 432Свойства минимальных многочленов...УтверждениеПусть в некотором поле Галуа 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).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждого β есть ровно один м.м.60 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждого β есть ровно один м.м.ДоказательствоПусть минимальных многочленов два.Они взаимно делят друг друга, а значит, различаются наобратимый множитель-константу.Поскольку минимальный многочлен нормирован, эта константаравна 1, т.е. многочлены совпадают.60 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем61 / 432Свойства минимальных многочленов...УтверждениеДля каждого элемента β поляне превосходит n.Fnp существует м.м.
и его степеньПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем61 / 432Свойства минимальных многочленов...УтверждениеДля каждого элемента β поляне превосходит n.Fnp существует м.м. и его степеньДоказательствоРассмотрим следующие элементы поля Fp : 1, β, β 2 , . . . , β n —их n + 1 штука, а размерность Fnp как векторного пространстваравна n ⇒ эти элементы линейно зависимы, т.е. существуюттакие не все равные 0 коэффициенты c0 , . .
. , cn , чтоc0 + c1 β + . . . + cn β n = 0.Таким образом, β — корень многочленаf (x) = c0 + c1 x + . . . + cn xn .Минимальным многочленом для β будет некоторыйнормированный неприводимый делитель f (x).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем62 / 432Многочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поляnмногочлена xp −1 − 1, т.е.xpгдеn −1Fnp является корнем− 1 = (x − β1 ) · . . . · (x − βpn −1 ),nβ1 , . .
. , βpn −1 = Fn∗p = Fp r {0}.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем62 / 432Многочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поляnмногочлена xp −1 − 1, т.е.xpгдеFnp является корнемn −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.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...СледствиеВсе элементы поля Fnp , не исключая нуля, являются корнямиnмногочлена xp − x.63 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем63 / 432Многочлены над конечным полем: свойства...СледствиеВсе элементы поля Fnp , не исключая нуля, являются корнямиnмногочлена xp − x.ДоказательствоВынесем x за скобку:nxp − x = x xpn −1−1 .У второго сомножителя корнями будут все ненулевыеэлементы, а у первого — 0.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема..(xn − 1) ..
(xm − 1) ⇔ n .. m.64 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема..(xn − 1) .. (xm − 1) ⇔ n .. m.ДоказательствоПусть n = mk. Сделаем замену: xm = y, тогдаxn − 1 = y k − 1 и xm − 1 = y − 1. Делимость очевидна,поскольку 1 является корнем y k − 1.64 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема..(xn − 1) .. (xm − 1) ⇔ n .. m.ДоказательствоПусть n = mk. Сделаем замену: xm = y, тогдаxn − 1 = y k − 1 и xm − 1 = y − 1. Делимость очевидна,поскольку 1 является корнем y k − 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 − 164 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Последнее выражение задает результат деления xn − 1 наxm − 1 с остатком, поскольку xmk − 1 делится на xm − 1 подоказанному выше.Остаток xr − 1 6= 0 в силу сделанных предположений.∴ xn − 1 не делится на xm − 1.65 / 432Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем65 / 432Многочлены над конечным полем: свойства...Последнее выражение задает результат деления xn − 1 наxm − 1 с остатком, поскольку xmk − 1 делится на xm − 1 подоказанному выше.Остаток xr − 1 6= 0 в силу сделанных предположений.∴ xn − 1 не делится на xm − 1.Теорема даёт возможность раскладывать многочлены xn − 1при составных n.Например, разложим x15 + 1 в поле характеристики 2(где −1 = +1):x15 + 1 = (x3 + 1)(x12 + x9 + x6 + x3 + 1),(3 | 15).Продолжить это разложение помогает следующая теорема.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем66 / 432Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xp − x.Fp [x] являютсяПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем66 / 432Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xp − x.Fp [x] являютсяДоказательствоn = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
