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

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

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

0.Прикладная алгебраПоля ГалуаЗадачиЗадачаПроизводная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.103 / 160Прикладная алгебраПоля ГалуаЗадачиЗадачаПроизводная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.Решениепроизводная монома (xn )0 = nxn−1 тождественно равна 0iff p | n;f 0 = 0 ⇒ показатели степеней всех мономов многочленаf делятся на p;поэтому f (x) = g(xp ) = g p (x).103 / 160Прикладная алгебраПоля ГалуаЗадачиЗадачаДоказать, что любая функция f :представлена многочленом.104 / 160Fnp → Fnp может бытьПрикладная алгебраПоля ГалуаЗадачи104 / 160ЗадачаДоказать, что любая функция f :представлена многочленом.Fnp → Fnp может бытьРешениеМожно, например, использовать интерполяционный многочленЛагранжа:QXb∈Fn r{a} (x − b)f (a) Q p.f (x) =(a − b)b∈Fnnp r{a}α∈FpПрикладная алгебраПоля ГалуаЗадачиЗадачаМногочлен x5 + x3 + x2 + 1 разложить на неприводимыемножители над полем вычетов по модулю 2.105 / 160Прикладная алгебраПоля ГалуаЗадачи105 / 160ЗадачаМногочлен x5 + x3 + x2 + 1 разложить на неприводимыемножители над полем вычетов по модулю 2.Решение1f (x) = x5 + x3 + x2 + 1, f (1) = 0 ⇒ 1 — корень f .2Делим f на x = 1, получаем x4 + x3 + x + 1 = f1 (x).3f1 (1) = 0 ⇒ 1 — корень f1 ;4f2 (1) = 0 ⇒ 1 — корень f2 ;5Многочлен x2 + x + 1 неприводим.f1x+1f2x+1= x3 + 1 = f2 (x).= x2 + x + 1.Ответ: x5 + x3 + x2 + 1 = (x + 1)3 (x2 + x + 1).Прикладная алгебраПоля ГалуаЗадачиЗадачаМногочлен f = x3 + 2x2 + 4x + 1 разложить на неприводимыемножители над полем F5 .106 / 160Прикладная алгебраПоля ГалуаЗадачи106 / 160ЗадачаМногочлен f = x3 + 2x2 + 4x + 1 разложить на неприводимыемножители над полем F5 .Решение1f (2) = 23 + 2 · 22 + 4 · 22 + 1 = 25 ≡5 0, (x − 2) ≡5 (x + 3)2x3 + 2x2 + 4x + 1x+3x3 + 3x2x2 + 4x + 24x2 + 4x4x2 + 2x2x + 12x + 103многочлен f1 = x2 + 4x + 2 неприводим вF5Ответ: x3 + 2x2 + 4x + 1 = (x + 3)(x2 + 4x + 2).Прикладная алгебраПоля ГалуаЗадачиЗадачаМногочлен f (x) = x4 + x3 + x + 2 разложить на неприводимыемножители над полем вычетов по модулю 3.107 / 160Прикладная алгебраПоля ГалуаЗадачи107 / 160ЗадачаМногочлен f (x) = x4 + x3 + x + 2 разложить на неприводимыемножители над полем вычетов по модулю 3.Решение1 0, 1, 2 — не корни f (x) ⇒ f (x) линейных делителей несодержит.2Неприводимые многочлены надF3 степени 2:x2 + 1,x2 + x + 2,x2 + 2x + 2.3Подбором получаем: f (x) = (x2 + 1)(x2 + x + 2).Ответ: (x2 + 1)(x2 + x + 2).Прикладная алгебраПоля ГалуаЗадачиЗадачаМногочлен x4 + 3x3 + 2x2 + x + 4 разложить на неприводимыемножители над полем вычетов по модулю 5.108 / 160Прикладная алгебраПоля ГалуаЗадачиЗадачаМногочлен x4 + 3x3 + 2x2 + x + 4 разложить на неприводимыемножители над полем вычетов по модулю 5.Решение12Убеждаемся, что многочлен f (x) = x4 + 3x3 + 2x2 + x + 4не имеет линейных делителей.Перебирая неприводимые многочлены степени 2 над F5 ,получаемf (x) = (x2 + x + 1)(x2 + 2x + 4).108 / 160Прикладная алгебраПоля ГалуаЗадачиЗадачаРазложить на неприводимые множители над полем вычетов помодулю 2 все нормированные многочлены второй степени от x.109 / 160Прикладная алгебраПоля ГалуаЗадачи109 / 160ЗадачаРазложить на неприводимые множители над полем вычетов помодулю 2 все нормированные многочлены второй степени от x.Решениеf1 = x2 = x · x,f2 = x2 + 1 = (x + 1)2 ,f3 = x2 + x = x · (x + 1),f4 = x2 + x + 1 — неприводим.Прикладная алгебраПоля ГалуаЗадачиЗадачаРазложить на неприводимые множители над полем вычетов домодулю 2 все нормированные многочлены третьей степени от x.110 / 160Прикладная алгебраПоля ГалуаЗадачи110 / 160ЗадачаРазложить на неприводимые множители над полем вычетов домодулю 2 все нормированные многочлены третьей степени от x.Решениеf1 = x3 ,f2 = x3 + 1 = (x + 1)(x2 + x + 1),f3 = x3 + x = x(x + 1)2 ,f4 = x3 + x2 = x2 (x + 1),f5 = x3 + x + 1 — неприводим,f6 = x3 + x2 + 1 — неприводим,f7 = x3 + x2 + x = x(x2 + x + 1),f8 = x3 + x2 + x + 1 = (x + 1)3 .Прикладная алгебраПоля ГалуаЗадачиЗадачаНайти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.111 / 160Прикладная алгебраПоля ГалуаЗадачи111 / 160ЗадачаНайти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.f1 = x2 + 1,f2 = x2 + x + 2,f3 = x2 + 2x + 2.Прикладная алгебраПоля ГалуаЗадачиЗадачаНайти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.112 / 160Прикладная алгебраПоля ГалуаЗадачи112 / 160ЗадачаНайти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.f1 = x3 + 2x + 1,f2 = x3 + 2x + 2,f3 = x3 + x2 + 2,f4 = x3 + 2x2 + 1,f5 = x3 + x2 + x + 2,f6 = x3 + x2 + 2x + 1,f7 = x3 + 2x2 + x + 1,f8 = x3 + 2x2 + 2x + 2.Прикладная алгебраПоля ГалуаЗадачиЗадача12Проверить, что F = F7 [x]/(x2 + x − 1) является полем.Выразить обратный к 1 − x в F в базисе { 1, x }.113 / 160Прикладная алгебраПоля ГалуаЗадачиЗадача12Проверить, что F = F7 [x]/(x2 + x − 1) является полем.Выразить обратный к 1 − x в F в базисе { 1, x }.Решение1f (x) = x2 + x − 1, f (0) = 6, f (1) = 1, f (2) = 5, f (3) = 4,f (4) = 6, f (5) = 1, f (6) = 6 ⇒многочлен f (x) — неприводим в F7 и F — поле (= F27 ).113 / 160Прикладная алгебраПоля ГалуаЗадачи113 / 160Задача12Проверить, что F = F7 [x]/(x2 + x − 1) является полем.Выразить обратный к 1 − x в F в базисе { 1, x }.Решение1f (x) = x2 + x − 1, f (0) = 6, f (1) = 1, f (2) = 5, f (3) = 4,f (4) = 6, f (5) = 1, f (6) = 6 ⇒многочлен f (x) — неприводим в F7 и F — поле (= F27 ).2F27= { ax + b | a, b ∈ F7 , x2 = 1 − x = 6x + 1 }(ax + b) · (6x + 1) = .

. . = (2a + 6b)x + (6a + b) = 16a + b = 1a=1⇒a + 3b = 0b=2Проверка: (6x + 1)(x + 2) = 6x2 + 13x + 2 = 1 + 7x = 1.Прикладная алгебраПоля ГалуаЗадачиЗадачаНайти порядок элемента x + x2 в мультипликативной группе12F2 [x]/(x4 + x + 1);поля F2 [x]/(x4 + x3 + 1).поля114 / 160Прикладная алгебраПоля ГалуаЗадачи114 / 160ЗадачаНайти порядок элемента x + x2 в мультипликативной группе12F2 [x]/(x4 + x + 1);поля F2 [x]/(x4 + x3 + 1).поляРешениеx + x2 = x(x + 1)1x4 = x + 1(x2 + x)2 = x4 + x2 = x2 + x + 1,(x2 + x)3 = x(x + 1)(x2 + x + 1) = x(x3 + 1) == x4 + x = x + 1 + x = 1.Ответ: 3.Прикладная алгебраПоля ГалуаЗадачи2115 / 160x4 = x3 + 1(x2 + x)2 = x4 + x2 = x3 + x2 + 1,(x2 + x)3 = x(x + 1)(x3 + x2 + 1) = x(x4 + x2 + x + 1) == x(x3 + x2 + x) = x4 + x3 + x2 = x2 + 1,(x2 + x)4 = (x2 + x)(x2 + x)3 = (x2 + x)(x2 + 1) == x4 + x2 + x3 + x = x3 + 1 + x2 + x3 + x == x2 + x + 1,...Прикладная алгебраПоля ГалуаЗадачиЗадачаНайти количество неприводимых многочленов123степени 7 над полем F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .116 / 160Прикладная алгебраПоля ГалуаЗадачи116 / 160ЗадачаНайти количество неприводимых многочленов123степени 7 над полем F2 ;степени 6 над полем F5 ;степени 24 над полем F3 .РешениеXmdm = pnm|n1dP7 =?mdm = 27 = 1 · d1 + 7 · d7 = 128.m|7d1 = 2 (x, x + 1) ⇒ d7 = (128 − 2)/7 = 126/7 = 18.Прикладная алгебраПоля ГалуаЗадачи117 / 160ЗадачаЧему равно произведение всех ненулевых элементов поляF62 ?Прикладная алгебраПоля ГалуаЗадачи117 / 160ЗадачаЧему равно произведение всех ненулевых элементов поляF62 ?РешениеВсе ненулевые элементы поля6 −1x2F62 являются корнями уравнения− 1 = x63 − 1 = 0 .По теореме Виета их произведение равно свободному члену,т.е.

−1 ≡2 1.(∗)Прикладная алгебраПоля ГалуаЗадачи118 / 160ЗадачаЧему равна сумма всех элементов поляF73 .Прикладная алгебраПоля ГалуаЗадачи118 / 160ЗадачаЧему равна сумма всех элементов поляF73 .РешениеВсе элементы поляF73 являются корнями уравнения7x3 − x = x2187 − x = 0 .(∗)По теореме Виета их сумма равна коэффициенту перед x2186 ,т.е. 0.Прикладная алгебраПоля ГалуаЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды119 / 160Прикладная алгебраПоля ГалуаЧто надо знатьРаздел IIКоды БЧХЧто надо знать120 / 160Прикладная алгебраПоля ГалуаЧто надо знатьКонечное поля и его характеристика. Мультипликативнаягруппа, примитивный элемент поля Галуа и егонахождение.

Основная теорема алгебры.Алгоритм Евклида и его применение. Теорема Безу ирасширенный алгоритм Евклида.Неприводимые многочлены: существование и нахождениенеприводимых многочленов в конечных полях. Построениеконечных полей с помощью неприводимых многочленов(привести пример). Изоморфизм конечных полей.Векторное пространство многочленов. Базис в Fnp . ПоляГалуа как векторные пространства. Подполя конечногополя.121 / 160Прикладная алгебраПоля ГалуаЧто надо знатьМинимальные многочлены над конечным полем: примерыи свойства. Корнями какого многочлена являются всеэлементы конечного поля? Делителями какого многочленаявляются все неприводимые многочлены n-й степени?Теорема о степени любого неприводимого делителяnмногочлена xp −1 − 1.Теорема о корнях неприводимого многочлена.

Многочленынад конечным полем: решение уравнений. Как решатьуравнения, когда корней нет?Мультипликативная группа расширения поля.Существование неприводимого многочлена степени n надполем Fp .Лемма о числе неприводимых нормированных многочленовиз Fnp . Среднее число неприводимых многочленов.Изоморфизм полей Галуа с одинаковым числом элементов.122 / 160Прикладная алгебраПоля ГалуаЧто надо знатьТеорема о неприводимом нормированном многочлене —делителе порождающего элемента идеала.Циклическое пространство: определение и примеры.Количество и степени неприводимых делителей xn − 1.123 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды124 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияРаздел IIКоды БЧХЧто надо знать125 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияДве задачиЕсть набор сообщений S1 , .

. . , St , которые нужно передать поканалу связи.Сообщения передаются в виде двоичных кодовых слов.126 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодированияДве задачиЕсть набор сообщений S1 , . . . , St , которые нужно передать поканалу связи.Сообщения передаются в виде двоичных кодовых слов.Ограничимся случаями, когда:12все сообщения кодируются словами одинаковой длины;ошибки при передаче могут только изменять значениянекоторых битов.126 / 160Прикладная алгебраКоды, исправляющие ошибкиОсновная задача теории кодирования126 / 160Две задачиЕсть набор сообщений S1 , .

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

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