Лекции по прикладной алгебре. v1.1 (1127111), страница 5

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

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

+ 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-й степени, что возможно лишь приb0 = b1 = . . . = bn−1 = 0, т.е. система { 1, x, . . . , xn−1 }линейно независима.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРасширение поляRЗамечаниеПостроение поля с помощью вычетов по модулю некоторогонеприводимого многочлена и аналоги доказанных теоремсправедливы не только в случае конечных полей.46 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРасширение поляRЗамечаниеПостроение поля с помощью вычетов по модулю некоторогонеприводимого многочлена и аналоги доказанных теоремсправедливы не только в случае конечных полей.Например:123рассмотрим поле действительных чисел R и кольцомногочленов R[x] над ним;в R[x] возьмём неприводимый многочлен x2 + 1;построим поле F как факторкольцо R[x]/(x2 + 1).46 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРасширение поляRЗамечаниеПостроение поля с помощью вычетов по модулю некоторогонеприводимого многочлена и аналоги доказанных теоремсправедливы не только в случае конечных полей.Например:123рассмотрим поле действительных чисел R и кольцомногочленов R[x] над ним;в R[x] возьмём неприводимый многочлен x2 + 1;построим поле F как факторкольцо R[x]/(x2 + 1).F также и векторное пространство над R; его базис — { 1, x } икаждый элемент F можно представить в виде a1 + bx, a, b ∈ R.Поле F изоморфно полю комплексных чиселC = { a + ib | a, b ∈ R, i2 = −1 }: изоморфизм задаётсясоответствием1 7→ 1, x 7→ i .46 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемПодполяFnpЛеммаЕсли полеFnp содержит подполе Fkp , то k | n.47 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемПодполяFnpЛеммаЕсли полеFnp содержит подполе Fkp , то k | n.ДоказательствоЕсли поле k1 содержится в поле k1 ⊂ k2 , то элементы k2можно умножать на элементы из k1 , а результаты складывать.Поэтому поле k2 является векторным пространством над полемk1 некоторой размерности d — значит, в нём |k1 |d элементов.Для нашего случая: pn = (pk )d , что и означает k | n.47 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды48 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемРаздел IIКоды БЧХЧто надо знать49 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМинимальный многочленРассмотрим поле Fnp , а в нём — какой-нибудь элемент β ибудем интересоваться многочленами, для которых этот элементявляется корнем.ОпределениеМногочлен m(x) называется минимальной функцией (илиминимальным многочленом, м.м.) для β, если m(x) —нормированный многочлен минимальной степени, для которогоβ является корнем.Другими словами, должны выполняться три свойства:123m(β) = 0;deg f (x) < deg m(x) ⇒ f (β) 6= 0;коэффициент при старшей степени в m(x) равен 1.50 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМинимальные многочлены: пример построенияРассмотрим Fnp = Fp [x]/(a(x)), гдеa(x) = a0 + a1 x + .

. . + an xn — неприводимый многочлен.Тогда для класса вычетов x ∈ Fnp многочлен a−1n a(x) —минимальный.51 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМинимальные многочлены: пример построенияРассмотрим 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 является корнем иan−1 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.51 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.52 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленовУтверждениеМинимальные многочлены неприводимы.ДоказательствоПусть m(x) — м.м. и m(x) = m1 (x)m2 (x).Имеемm1 (β) = 0m(β) = 0 ⇒,m2 (β) = 0но deg m1 < m(x) и deg m2 < m(x), что противоречитминимальности m(x).52 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеПусть f (x) — многочлен, а m(x) — м.м. для β в некотором полеГалуа и f (β) = 0.Тогда f (x) делится на m(x).53 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем53 / 160Свойства минимальных многочленов...УтверждениеПусть f (x) — многочлен, а m(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).Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждого β есть ровно одна минимальная функция.54 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...СледствиеДля каждого β есть ровно одна минимальная функция.ДоказательствоДействительно, пусть минимальных функций две.Они взаимно делят друг друга, а значит, различаются наобратимый множитель (константу).Поскольку минимальная функция нормирована, эта константаравна 1, т.

е. функции совпадают.54 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеДля каждого β ∈ Fnp существует м.м. и его степень непревосходит n.55 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемСвойства минимальных многочленов...УтверждениеДля каждого β ∈ Fnp существует м.м. и его степень непревосходит n.ДоказательствоРассмотрим следующие элементы поля 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).55 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем56 / 160Многочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поляnмногочлена xp −1 − 1, т.е.xpn −1Fnp является корнем− 1 = (x − β1 ) · . .

. · (x − βpn −1 ),где { β1 , . . . , βpn −1 } =Fn∗p=Fnp r {0}.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем56 / 160Многочлены над конечным полем: свойстваТеоремаЛюбой ненулевой элемент поляnмногочлена xp −1 − 1, т.е.xpn −1Fnp является корнем− 1 = (x − β1 ) · . .

. · (x − βpn −1 ),где { β1 , . . . , βpn −1 } =Fn∗p=Fnp 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.57 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем57 / 160Многочлены над конечным полем: свойства...СледствиеВсе элементы поля Fnp , не исключая нуля, являются корнямиnмногочлена xp − x.ДоказательствоВынесем x за скобку:nxp − x = x xpn −1−1 .У второго сомножителя корнями будут все ненулевыеэлементы, а у первого — 0.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема..(xn − 1) ..

(xm − 1) ⇔ n .. m.58 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема..(xn − 1) .. (xm − 1) ⇔ n .. m.ДоказательствоПусть n = mk. Сделаем замену: xm = y, тогдаxn − 1 = y k − 1 и xm − 1 = y − 1. Делимость очевидна,поскольку 1 является корнем y k − 1.58 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Теорема..(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 − 158 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полемМногочлены над конечным полем: свойства...Последнее выражение задает результат деления xn − 1 наxm − 1 с остатком, поскольку xmk − 1 делится на xm − 1 подоказанному выше.Остаток xr − 1 6= 0 в силу сделанных предположений.∴ xn − 1 не делится на xm − 1.59 / 160Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем59 / 160Многочлены над конечным полем: свойства...Последнее выражение задает результат деления 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).Продолжить это разложение помогает следующая теорема.Прикладная алгебраПоля ГалуаКорни многочленов над конечным полем60 / 160Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xp − x.Fp [x] являютсяПрикладная алгебраПоля ГалуаКорни многочленов над конечным полем60 / 160Многочлены над конечным полем...ТеоремаВсе неприводимые многочлены n-й степени изnделителями xp − x.Fp [x] являютсяДоказательствоn = 1.

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

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