AA3-1(GF-II) (1127139), страница 3
Текст из файла (страница 3)
Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваКоличество и степени неприводимых делителей xn − 1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ⇒30 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваКоличество и степени неприводимых делителей xn − 1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ⇒ поле Fq содержитгруппу корней из единицы степени n iff n | (q − 1).Чтобы вернуться от разложения xn − 1 на линейныемножители в поле Fq = Fnp (корни из 1) к разложению нанеприводимые множители в поле Fp , нужно понять, какиекорни из единицы будут входить в неприводимый делительf (x).2Если β — корень f (x), то β p , β p и т.д.
— также его корни⇒ количество и степени неприводимых делителей xn − 1можно найти, разбив Fp на орбиты отображенияt 7→ pt mod n.30 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваРазложение многочлена x15 − 1 над полем31 / 78F2ПримерРассмотрим ещё раз разложение многочлена x15 − 1 надОтносительно умножения на 2 вычеты по модулю 15разбиваются на такие орбиты:F2 .{ 0 }, { 1, 2, 4, 8 }, { 3, 6, 12, 9 }, { 5, 10 }, { 7, 14, 13, 11 }(12 · 2 = 24 = 15 + 9)Поэтому x15 − 1 разлагается в произведениеодного неприводимого многочлена степени 1,одного неприводимого многочлена степени 2,трех неприводимых многочленов степени 4.Конкретно (разложение было раньше): x15 + 1 == (x + 1)(x2 + x + 1)(x4 + x + 1)(x4 + x3 + 1)(x4 + x3 + x2 + x + 1).ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЦиклические подпространстваРазложение многочлена x23 − 1 над полем32 / 78F2ПримерРассмотрим разложение многочлена x23 − 1 над F2 .Относительно умножения на 2 вычеты по модулю 23разбиваются на три орбиты:{ 0 }, { 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12 },{ 5, 10, 20, 17, 11, 22, 21, 19, 15, 7, 14 }(18 · 2 = 36 ≡23 13)Поэтому x23 − 1 разлагается в произведение одногонеприводимого многочлена степени 1 и двух неприводимыхмногочленов степени 11.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать33 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-1 (теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.34 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-1 (теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.Решениеp = 2: — утверждение тривиально.34 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-1 (теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.Решениеp = 2: — утверждение тривиально.p > 2: Степени всех элементов мультипликативной циклическойгруппы F∗p = { 1, .
. . , p − 1 } делят её порядокp − 1 ⇔ ∀ x ∈ F∗p : xp−1 = 1 ⇒ все они являютсякорнями уравнения xp−1 − 1 = 0.Других корней у этого уравнения нет (многочлен степениp − 1 имеет не больше p − 1 корней).По теореме Виета их произведение равно свободномучлену, т.е.
−1.34 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-2Найти x ≡17 12006 + 22006 + . . . + 162006 .35 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями35 / 78Задача ПГ-2Найти x ≡17 12006 + 22006 + . .
. + 162006 .РешениеРассмотрим мультипликативную циклическую группу{ 1, 2, . . . , 16 } поля F17 ;G = 12006 , 22006 , . . . , 162006 — циклическая подгруппапорядка k (здесь только k несовпадающих элементов,k | 16) этой группы.Элементы G — корни уравненияxk − 1 = 0(∗)Их сумма по теореме Виета есть коэффициент при xk−1 в(∗), т.е. 0.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-3Построить поле из 4-х элементов.36 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениями36 / 78Задача ПГ-3Построить поле из 4-х элементов.РешениеЭто поле F22 , оно может быть построено как фактор-кольцоF2 [x]/ (a(x)), где a(x) — неприводимый многочлен из F2 [x]степени 2.Но такой многочлен только один: x2 + x + 1.Следовательно, F22 = { 0, 1, x, x + 1 }Таблицы сложения и умножения в поле:+1xx+1×10x+1x1xx+101xx+1x10x+111xx+1xxx+11x+1x+11xПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-4Производная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.37 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями37 / 78Задача ПГ-4Производная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.Решениепроизводная монома (xn )0 = nxn−1 тождественно равна 0iff n ≡p 0 ⇔ p | n;f 0 = 0 ⇒ показатели степеней всех мономов многочленаf делятся на p;поэтому f (x) = g(xp ) = g p (x).ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-5Доказать, что любая функция f :представлена многочленом.Fnp → Fnp может быть38 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями38 / 78Задача ПГ-5Доказать, что любая функция f :представлена многочленом.Fnp → Fnp может бытьРешениеМожно, например, использовать интерполяционный многочленЛагранжа:Q(x − b)Xb ∈ Fnp r{a}Q.f (x) =f (a)(a − b)na ∈ Fpb ∈ Fnp r{a}ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-6Многочлен x5 + x3 + x2 + 1 разложить на неприводимыемножители над полем вычетов по модулю 2.39 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-6Многочлен x5 + x3 + x2 + 1 разложить на неприводимыемножители над полем вычетов по модулю 2.Решение1f (x) = x5 + x3 + x2 + 1, f (1) = 0 ⇒ 1 — корень f .2Делим f (x) на x − 1, получаем x4 + x3 + x + 1 = f1 (x).3f1 (1) = 0 ⇒ 1 — корень f1 ;f1x+1= x3 + 1 = f2 (x).4f2 (1) = 0 ⇒ 1 — корень f2 ;f2x+1= x2 + x + 1.5Многочлен x2 + x + 1 неприводим.Ответ: x5 + x3 + x2 + 1 = (x + 1)3 (x2 + x + 1).39 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-7Многочлен f (x) = x3 + 2x2 + 4x + 1 ∈ F5 [x] разложить нанеприводимые множители.40 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями40 / 78Задача ПГ-7Многочлен f (x) = x3 + 2x2 + 4x + 1 ∈ F5 [x] разложить нанеприводимые множители.Решение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).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-8Многочлен f (x) = x4 + x3 + x + 2 ∈ F3 [x] разложить нанеприводимые множители.41 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениямиЗадача ПГ-8Многочлен f (x) = x4 + x3 + x + 2 ∈ F3 [x] разложить нанеприводимые множители.Решение10, 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).41 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями42 / 78Задача ПГ-9Многочлен x4 + 3x3 + 2x2 + x + 4 разложить на неприводимыемножители над полем вычетов по модулю 5.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями42 / 78Задача ПГ-9Многочлен x4 + 3x3 + 2x2 + x + 4 разложить на неприводимыемножители над полем вычетов по модулю 5.Решение1.
Убеждаемся, что многочлен f (x) = x4 + 3x3 + 2x2 + x + 4не имеет линейных делителей:f (x) 6= 0 ни при одном x = 0, 1, 2, 3, 4.2. Перебирая неприводимые многочлены степени 2 надполучаемf (x) = (x2 + x + 1)(x2 + 2x + 4).F5 ,ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями43 / 78Задача ПГ-10Разложить на неприводимые множители над полем вычетов помодулю 2 все нормированные многочлены второй степени от x.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениями43 / 78Задача ПГ-10Разложить на неприводимые множители над полем вычетов помодулю 2 все нормированные многочлены второй степени от x.Решениеf1 (x) = x2 = x · x,f2 (x) = x2 + 1 = (x + 1)2 ,f3 (x) = x2 + x = x · (x + 1),f4 (x) = x2 + x + 1 — неприводим.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-11Разложить на неприводимые множители все нормированныемногочлены третьей степени из F2 [x].44 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-11Разложить на неприводимые множители все нормированныемногочлены третьей степени из F2 [x].Решениеf1 (x) = x3 ,f2 (x) = x3 + 1 = (x + 1)(x2 + x + 1),f3 (x) = x3 + x = x(x + 1)2 ,f4 (x) = x3 + x2 = x2 (x + 1),f5 (x) = x3 + x + 1 — неприводим,f6 (x) = x3 + x2 + 1 — неприводим,f7 (x) = x3 + x2 + x = x(x2 + x + 1),f8 (x) = x3 + x2 + x + 1 = (x + 1)3 .44 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-12Найти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.45 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-12Найти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.45 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IIЗадачи с решениями45 / 78Задача ПГ-12Найти все нормированные многочлены второй степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.Перебором коэффициентов в выражении x2 + bx + c, находимподходящие многочлены:f1 (x) = x2 + 1,f2 (x) = x2 + x + 2,f3 (x) = x2 + 2x + 2.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-13Найти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.46 / 78ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-13Найти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.46 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЗадачи с решениямиЗадача ПГ-13Найти все нормированные многочлены третьей степени от x,неприводимые над полем вычетов по модулю 3.РешениеДолжно быть: f (0) 6= 0, f (1) 6= 0, f (2) 6= 0.f1 (x) = x3 + 2x + 1,f2 (x) = x3 + 2x + 2,f3 (x) = x3 + x2 + 2,f4 (x) = x3 + 2x2 + 1,f5 (x) = x3 + x2 + x + 2,f6 (x) = x3 + x2 + 2x + 1,f7 (x) = x3 + 2x2 + x + 1,f8 (x) = x3 + 2x2 + 2x + 2.46 / 78ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
