PA_full (PDF-лекции от Гурова)

Прикладная алгебра1 / 432Прикладная алгебраЛекции для III потока,5-й семестрЛектор � Гуров Сергей Исаевичассистент � Кропотов Дмитрий АлександровичФакультет Вычислительной математики и кибернетики,МГУ имени М.В. ЛомоносоваКафедра Математических методов прогнозированиякомн. 530, 682e-mail: sgur@cs.msu.ruПрикладная алгебраЛитератураВоронин В.П. Дополнительные главы дискретнойматематики.

� М.: ф-т ВМК МГУ, 2002.http://padabum.com/d.php?id=10281Гуров С.И. Булевы алгебры, упорядоченные множества,решетки: Определения, свойства, примеры. � М.: Либроком,2013.Журавлёв Ю.И., Флёров Ю.А., Вялый М.Н. Дискретныйанализ. Основы высшей алгебры. � М.: МЗ Пресс, 2007.Лидл Р., Нидеррайтер Г.

Конечные поля: В 2-х т. � М.: Мир,1988.Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов,исправляющих ошибки. � М.: Связь, 1979.Нефедов В.Н., Осипова В.А. Курс дискретной математики. �М.: Изд-во МАИ, 1992.Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. � М.:Мир, 1976.2 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.

Коды ХэммингаГрупповые (линейные) коды3 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств4 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать5 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа6 / 432Поле GF (p)� евклидово кольцо целых чисел (без делителей нуля +деление с остатком); p � простое число.(p) = {np | n 2 } = p = {0, ±p, ±2p, .

. .} � идеал/(p) � кольцо вычетов по модулю этого идеала �/(p) = 0, 1, . . . , p 1 � классы остатков от деления на p:01...p 1= 0+p ,= 1+p ,= (p1) + p .9>>=>>;)= 0 [ 1 [ ... [ pЧасто черту над символами классов вычетов не пишут.1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа6 / 432Поле GF (p)� евклидово кольцо целых чисел (без делителей нуля +деление с остатком); p � простое число.(p) = {np | n 2 } = p = {0, ±p, ±2p, . . .} � идеал/(p) � кольцо вычетов по модулю этого идеала �/(p) = 0, 1, . . . , p 1 � классы остатков от деления на p:01...p 1= 0+p ,= 1+p ,= (p1) + p .9>>=>>;)= 0 [ 1 [ ...

[ p1.Часто черту над символами классов вычетов не пишут.Поскольку p � простое, то /(p) � не просто кольцо, а поле(возможно деление без остатка на любой ненулевой элемент).Это простейшее поле Галуа, обозначение � p или GF (p) (всеоперации в нём � по mod p).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПоле3:3= /(3) и факторкольцо+0120012112022017 / 432/(4)⇥012000010122021Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПоле3:/(4) :37 / 432= /(3) и факторкольцо+012001211202201+012300123112302230133012/(4)⇥012000010122021⇥012300000101232020230321Дважды два равно нулю!Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаХарактеристика поляПусть � произвольное поле, 1 � единица .

Складываем их:1 = 1 , 2 = 1 + 1 , . . ..8 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа8 / 432Характеристика поляПусть � произвольное поле, 1 � единица . Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1. . + 1} = 0. Тогда| + .{zk разk = порядок аддитивной группы поля== характеристика поляdef= charПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа8 / 432Характеристика поляПусть � произвольное поле, 1 � единица .

Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1. . + 1} = 0. Тогда| + .{zk разk = порядок аддитивной группы поля== характеристика поля{ 1, 2, . . . , chardef= char1, 0 } � минимальное подполе в поле .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа8 / 432Характеристика поляПусть � произвольное поле, 1 � единица . Складываем их:1 = 1 , 2 = 1 + 1 , . . ..

В конечном поле всегда найдётсяпервое k такое, что 1. . + 1} = 0. Тогда| + .{zk разk = порядок аддитивной группы поля== характеристика поля{ 1, 2, . . . , chardef= char1, 0 } � минимальное подполе в поле .Если все суммы вида 1 + . . . + 1 различны, то char = 0.Примеры: , � поля нулевой (или бесконечной :))характеристики.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикой9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикой� произвольное (конечное или бесконечное) поле.

Построим:1[x] � кольцо многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an 2 от формальной переменной x.9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикой� произвольное (конечное или бесконечное) поле. Построим:12[x] � кольцо многочленов P (x) = a0 + a1 x + .

. . + an xn ,a0 , . . . , an 2 от формальной переменной x.(x) � поле рациональных функций над9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикой� произвольное (конечное или бесконечное) поле. Построим:12[x] � кольцо многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an 2 от формальной переменной x.(x) � поле рациональных функций над ; в нём:элементы � “дроби” P/Q (если Q 6= 0), где P, Q 2 [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 );включение � Поскольку [x] ⇢ (x), то каждыймногочлен P отождествляется с P/1.9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикой� произвольное (конечное или бесконечное) поле.

Построим:12[x] � кольцо многочленов P (x) = a0 + a1 x + . . . + an xn ,a0 , . . . , an 2 от формальной переменной x.(x) � поле рациональных функций над ; в нём:элементы � “дроби” P/Q (если Q 6= 0), где P, Q 2 [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 );включение � Поскольку [x] ⇢ (x), то каждыймногочлен P отождествляется с P/1.Если в качестве взять конечное поле p , то p (x) �бесконечное поле положительной характеристики p.9 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаСильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .10 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа10 / 432Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap1b+ .

. . + Cpp1abp1+ bp .Но при i = 1, . . . , p 1 числитель коэффициента Cpi =делится на p, а знаменатель � нет, ) Cpi ⌘p 0.p!i!(p i)!Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа10 / 432Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap1b+ . . . + Cpp1abp1+ bp .Но при i = 1, . . .

, p 1 числитель коэффициента Cpi =делится на p, а знаменатель � нет, ) Cpi ⌘p 0.p!i!(p i)!СледствиеnnnВ поле характеристики p > 0 справедливо (a + b)p = ap + bp .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа11 / 432Мультипликативная группа и примитивный элемент поля⇤ defp =pr {0} � мультипликативная группа поляp.pПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа11 / 432Мультипликативная группа и примитивный элемент поля⇤ defp =pr {0} � мультипликативная группа поляУтверждение⇤ � циклическая группа порядка ppp.1 по умножению.pПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа11 / 432Мультипликативная группа и примитивный элемент поля⇤ defp =pr {0} � мультипликативная группа поляУтверждение⇤ � циклическая группа порядка ppp.1 по умножению.Как любая конечная циклическая группа,генератор = примитивный элемент ↵:⇤pсодержитлюбой элемент 2 ⇤p является некоторой его натуральнойстепенью � т.е.= ↵i , i 2 { 1, . .

. , p 1};причём 1 = ↵p 1 � т.е. ↵i 6= 1 для 1 6 i 6 p 2.pПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа11 / 432Мультипликативная группа и примитивный элемент поля⇤ defp =pr {0} � мультипликативная группа поляУтверждение⇤ � циклическая группа порядка ppp.1 по умножению.Как любая конечная циклическая группа,генератор = примитивный элемент ↵:⇤pсодержитлюбой элемент 2 ⇤p является некоторой его натуральнойстепенью � т.е.= ↵i , i 2 { 1, . . . , p 1};причём 1 = ↵p 1 � т.е. ↵i 6= 1 для 1 6 i 6 p 2.УтверждениеГруппа⇤pимеет '(p1) примитивных элементов.pПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаФункция Эйлера'(n) � функция Эйлера � количество чисел из интервала[ 1, . .

. , n 1 ], взаимно простых с n:'(1) = 1 (по определению), '(2) = 1, '(3) = '(4) = 2,'(5) = 4, '(6) = {1, 5} = 2, . . .12 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа12 / 432Функция Эйлера'(n) � функция Эйлера � количество чисел из интервала[ 1, . . . , n 1 ], взаимно простых с n:'(1) = 1 (по определению), '(2) = 1, '(3) = '(4) = 2,'(5) = 4, '(6) = {1, 5} = 2, . . .Свойства (p � простое число)'(n) 6 n 1 и '(p) = p'(nm )=nm 1 '(n),т.е.d'(m)'(n) '(d),1;'(pm )= pm1 (p1);'(mn) =где d = НОД(m, n),откуда: если m и n взаимно просты, то'(mn) = '(m)'(n) ('(·) � мультпликативная функция).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа12 / 432Функция Эйлера'(n) � функция Эйлера � количество чисел из интервала[ 1, . .

. , n 1 ], взаимно простых с n:'(1) = 1 (по определению), '(2) = 1, '(3) = '(4) = 2,'(5) = 4, '(6) = {1, 5} = 2, . . .Свойства (p � простое число)'(n) 6 n 1 и '(p) = p'(nm )=nm 1 '(n),т.е.1;'(pm )= pm1 (p1);d'(m)'(n) '(d),'(mn) =где d = НОД(m, n),откуда: если m и n взаимно просты, то'(mn) = '(m)'(n) ('(·) � мультпликативная функция).Пример:'(15) = '(3 · 5) = '(3)'(5) = (343'(16) = '(2 ) = 2 '(2) = 8.1)(51) = 8,Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПервые 99 значений функции Эйлера и степенипримитивного элемента13 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа13 / 432Первые 99 значений функции Эйлера и степенипримитивного элементаДля примитивного элемента ↵ мультипликативной группы↵p1= 1 ) ↵p = ↵1 = ↵ и ↵Например, в5: ↵16= ↵4 ,1=↵1· ↵p1= ↵p2.⇤:pПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа13 / 432Первые 99 значений функции Эйлера и степенипримитивного элементаДля примитивного элемента ↵ мультипликативной группы↵p1= 1 ) ↵p = ↵1 = ↵ и ↵Например, в5: ↵16= ↵4 , ↵11=↵= ↵3 .1· ↵p1= ↵p2.⇤:pПрикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаКак найти примитивные элементы поля14 / 432p?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа14 / 432Как найти примитивные элементы поляЕсли примарное разложение (p1) �p?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа14 / 432Как найти примитивные элементы поляЕсли примарное разложение (pизвестно � элемент ↵ 2↵p 1qpp?1) �будет примитивным iff6⌘p 1 для каждого q | (p1).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа14 / 432Как найти примитивные элементы поляЕсли примарное разложение (pизвестно � элемент ↵ 2↵p 1qpp?1) �будет примитивным iff6⌘p 1 для каждого q | (p1).неизвестно � эффективного алгоритма нахожденияпримитивного элемента не найдено (используютвероятностные алгоритмы).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа14 / 432Как найти примитивные элементы поляЕсли примарное разложение (pизвестно � элемент ↵ 2↵p 1qpp?1) �будет примитивным iff6⌘p 1 для каждого q | (p1).неизвестно � эффективного алгоритма нахожденияпримитивного элемента не найдено (используютвероятностные алгоритмы).Если ↵ � примитивный элемент поля p , то любой другой егопримитивный элемент может быть получен как степень ↵k , гдеk � целое число, взаимно простое с p 1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа15 / 432Неприводимые многочленыУтверждениеКольцо многочленов [x] над полем� евклидово.ТеоремаКаждый элемент евклидова кольца однозначно с точностью доперестановок разлагается в произведение простых элементов.