Лекции по прикладной алгебре. v1.1 (1127111)
Текст из файла
Прикладная алгебра1 / 160Прикладная алгебраЛекции для групп 320–328 (III поток)5-й семестр 2013/2014 уч. годаЛектор — Гуров Сергей ИсаевичАссистент — Кропотов Дмитрий АлександровичФакультет Вычислительной математики и кибернетики,МГУ имени М.В. ЛомоносоваКафедра Математических методов прогнозированиякомн. 530, 682e-mail: sgur@cs.msu.ruПрикладная алгебраЛитератураВоронин В. П.
Дополнительные главы дискретнойматематики. — М.: ф-т ВМК МГУ, 2002.http://padabum.com/d.php?id=10281Гуров С. И. Булевы алгебры, упорядоченные множества,решетки: Определения, свойства, примеры. — М.: Либроком,2013.Журавлёв Ю. И., Флёров Ю. А., Вялый М. Н. Дискретныйанализ. Основы высшей алгебры. — М.: МЗ Пресс, 2007.Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т.
— М.: Мир,1988.Нефедов В. Н., Осипова В. А. Курс дискретной математики. —М.: Изд-во МАИ, 1992.2 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды3 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел IIКоды БЧХЧто надо знать4 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа5 / 160Поле GF (p)Z — евклидово кольцо целых чисел (без делителей нуля +деление с остатком).p — простое число.(p) = {np | n ∈ Z} = pZ = {0, ±p, ±2p, .
. .} — идеалZ/pZ — кольцо вычетов по модулю этого идеала:Z/pZ = {0, 1, . . . , p − 1} — классы остатков от деления на p:0 = 0 + pZ ,1 = 1 + pZ ,...p − 1 = (p − 1) + pZ .Z= 0 ∪ 1 ∪ . . . ∪ p − 1.Поскольку p — простое, то Z/pZ — поле.Это простейшее поле Галуа, обозначение —Все операции в поле Fp — по mod p.Fp или GF (p).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПолеF3 :F3и факторкольцо+0120012112022016 / 160Z/4Z·012000010122021Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПолеF36 / 160и факторкольцоF3 :+012001211202201Z/4Z :+012300123112302230133012Z/4Z·012000010122021·012300000101232020230321Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаХарактеристика поляПусть k — произвольное поле, 1 — единица k.
Складываем их:1 = 1 , 2 = 1 + 1 , . . ..7 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа7 / 160Характеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. . + 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdefПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа7 / 160Характеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , .
. .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. . + 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdef{ 1, 2, . . . , char k − 1, 0 } — минимальное подполе в поле k. Есливсе суммы 1. . + 1} различны, то char k = 0.| + .{zПримеры: Q, R.kПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМожет ли бесконечное поле иметь положительнуюхарактеристику?8 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМожет ли бесконечное поле иметь положительнуюхарактеристику?k — произвольное (конечное или бесконечное) поле.
Построим:1k[x] — множество многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an ∈ k от x с коэффициентами из k.8 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМожет ли бесконечное поле иметь положительнуюхарактеристику?k — произвольное (конечное или бесконечное) поле. Построим:12k[x] — множество многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . .
. , an ∈ k от x с коэффициентами из k.k(x) — поле рациональных функций над k.8 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМожет ли бесконечное поле иметь положительнуюхарактеристику?k — произвольное (конечное или бесконечное) поле. Построим:12k[x] — множество многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , .
. . , an ∈ k от x с коэффициентами из k.k(x) — поле рациональных функций над k. В нёмЭлементы — “дроби” P/Q (если Q 6= 0), где P, Q ∈ k[x].Умножение — P/Q · U/V = (P U )/(QV ).Эквивалентность — P1 /Q1 = P2 /Q2 , если P1 Q2 = P2 Q1 .Сложение — дроби можно приводить к общемузнаменателю и складывать:P/Q+U/V = (P V )/(QV )+(QU )/(QV ) = (P V +QU )/(QV ).Включение — Поскольку k[x] ⊂ k(x), то каждыймногочлен P отождествляется с P/1.8 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа8 / 160Может ли бесконечное поле иметь положительнуюхарактеристику?k — произвольное (конечное или бесконечное) поле.
Построим:12k[x] — множество многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an ∈ k от x с коэффициентами из k.k(x) — поле рациональных функций над k. В нёмЭлементы — “дроби” P/Q (если Q 6= 0), где P, Q ∈ k[x].Умножение — P/Q · U/V = (P U )/(QV ).Эквивалентность — P1 /Q1 = P2 /Q2 , если P1 Q2 = P2 Q1 .Сложение — дроби можно приводить к общемузнаменателю и складывать:P/Q+U/V = (P V )/(QV )+(QU )/(QV ) = (P V +QU )/(QV ).Включение — Поскольку k[x] ⊂ k(x), то каждыймногочлен P отождествляется с P/1.Если в качестве k взять конечное полебесконечное поле с характеристикой p.Fp , то Fp (x) —Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .9 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа9 / 160Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap−1 b + .
. . + Cpp−1 abp−1 + bp .Но при i = 1, . . . , p − 1 числитель Cpi =знаменатель — нет, ∴ Cpi ≡p 0.p!i!(p−i)!делятся на p, аПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа9 / 160Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap−1 b + . . . + Cpp−1 abp−1 + bp .Но при i = 1, .
. . , p − 1 числитель Cpi =знаменатель — нет, ∴ Cpi ≡p 0.p!i!(p−i)!делятся на p, аСледствиеnnnВ поле характеристики p > 0 справедливо (a + b)p = ap + bp .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗p= Fp r {0} = { 1, . . .
, p − 1 } — мультипликативная группаполя Fp .def10 / 160FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗p= Fp r {0} = { 1, . . . , p − 1 } — мультипликативная группаполя Fp .defУтверждениеF∗p — циклическая группа порядка p − 1 по умножению.10 / 160FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗p= Fp r {0} = { 1, .
. . , p − 1 } — мультипликативная группаполя Fp .defУтверждениеF∗p — циклическая группа порядка p − 1 по умножению.F∗p содержит примитивный элемент α —порядок α равен p − 1, т.е.αp−1 = 1 и αi 6= 1 для 0 < i < p − 1.любой ненулевой элемент β ∈ F∗p является некоторойстепенью примитивного элемента:β = αi , i = 0, 1, . . . , q − 1.10 / 160FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗p= Fp r {0} = { 1, . . .
, p − 1 } — мультипликативная группаполя Fp .defУтверждениеF∗p — циклическая группа порядка p − 1 по умножению.F∗p содержит примитивный элемент α —порядок α равен p − 1, т.е.αp−1 = 1 и αi 6= 1 для 0 < i < p − 1.любой ненулевой элемент β ∈ F∗p является некоторойстепенью примитивного элемента:β = αi , i = 0, 1, . .
. , q − 1.УтверждениеГруппаF∗p имеет ϕ(p − 1) примитивных элементов.10 / 160FpПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера т.е. количество чисел ряда изинтервала [ 1, . . . , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = |{1, 5}| = 2, .
. .11 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера т.е. количество чисел ряда изинтервала [ 1, . . . , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = |{1, 5}| = 2, . . .Свойства:ϕ(n) 6 n − 1 и ϕ(p) = p − 1, если p — простое;ϕ(nm ) = nm−1 ϕ(n), т.е. ϕ(pm ) = pm−1 (p − 1), если p —простое;если m и n взаимно просты, то ϕ(m · n) = ϕ(m) · ϕ(n)(т.е.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
