AA3-1(GF-I) (1127138), страница 4
Текст из файла (страница 4)
в F2 [x], и он принадлежит F .Является ли P (x) — примитивным элементом поля F ?Мультипликативная группа поля F содержит 23 − 1 = 7элементов, это простое число ⇒ в мультипликативная группевсе ϕ(7) = 6 неединичных элеметов — генераторы ⇒ответ на оба вопроса — ДА!25 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаВсегда ли неприводимый многочлен есть примитивныйэлемент?26 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаВсегда ли неприводимый многочлен есть примитивныйэлемент?F5= { 0, 1, 2, 3, 4 }.1Возьмём поле2Возьмём неприводимый над34F5многочлен x2 + x + 1.Построим поле F = F5 [x]/ x2 + x + 1 ∼= F25 ; оносодержит только полиномы 0-й и 1-й степеней из F5 [x].Все многочлены 1-й степени неприводимы, имеют видax + b и их — 20 шт.Все ли они — примитивные элементы поля F ?26 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаВсегда ли неприводимый многочлен есть примитивныйэлемент?F5= { 0, 1, 2, 3, 4 }.1Возьмём поле2Возьмём неприводимый над34F5многочлен x2 + x + 1.Построим поле F = F5 [x]/ x2 + x + 1 ∼= F25 ; оносодержит только полиномы 0-й и 1-й степеней из F5 [x].Все многочлены 1-й степени неприводимы, имеют видax + b и их — 20 шт.Все ли они — примитивные элементы поля F ?Мультипликативная группа поля F содержит 52 − 1 = 24элемента из которых ϕ(24) = 8 примитивных ⇒ не всемногочлены 1-й степени — генераторы ⇒ответ на оба вопроса — НЕТ!26 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКогда x есть примитивный элемент?Вопрос: когда корень x (сам неприводимый многочлен!)неприводимого над Fp многочлена a(x) будет примитивнымэлементом мультипликативной группы поля Fp [x]/(a(x))?27 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаКогда x есть примитивный элемент?Вопрос: когда корень x (сам неприводимый многочлен!)неприводимого над Fp многочлена a(x) будет примитивнымэлементом мультипликативной группы поля Fp [x]/(a(x))?Ответ: корень нормированного неприводимого многочленаa(x) будет примитивным элементом мультипликативнойгруппы поля Fp [x]/(a(x)) iff a(x) примитивен, т.е.t = pn − 1 — наименьший показатель, при которомa(x) | xt − 1 (или, эквивалентно, a(x) — м.м.
для x).Пример: неприводимый над F2 многочлен x3 + x + 13примитивен: (x2 −1 + 1)/(x3 + x + 1) = x4 + x2 + x + 1, но.xm + 1 6 .. x3 + x + 1 ни при каком m = 4, 5, 6. ПоэтомуF∗2 [x]/x3 + x + 1 = { x0 = 1, x, x2 ,x3 = x + 1, x4 = x2 + x, x5 = x2 + x + 1, x6 = x2 + 1} .27 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать28 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IВычисление элементов в конечных поляхАлгоритм Евклида —— применяют для нахождения НОД(a, b) натуральных a и b.Наблюдение: общий делитель пары чисел (a, b), то остаётся ими для пары (a − b, b) (считаем, что a > b).29 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IВычисление элементов в конечных поляхАлгоритм Евклида —— применяют для нахождения НОД(a, b) натуральных a и b.Наблюдение: общий делитель пары чисел (a, b), то остаётся ими для пары (a − b, b) (считаем, что a > b).Отсюда:пары чисел (a, b) и (a − kb, b) (q ∈ Z) имеет одинаковыеобщие делители;29 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхАлгоритм Евклида —— применяют для нахождения НОД(a, b) натуральных a и b.Наблюдение: общий делитель пары чисел (a, b), то остаётся ими для пары (a − b, b) (считаем, что a > b).Отсюда:пары чисел (a, b) и (a − kb, b) (q ∈ Z) имеет одинаковыеобщие делители;вместо a − kb можно взять остаток r0 от деления нацелоa на b : a = bq + r0 , q ∈ Z, 0 6 r0 < b;29 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхАлгоритм Евклида —— применяют для нахождения НОД(a, b) натуральных a и b.Наблюдение: общий делитель пары чисел (a, b), то остаётся ими для пары (a − b, b) (считаем, что a > b).Отсюда:пары чисел (a, b) и (a − kb, b) (q ∈ Z) имеет одинаковыеобщие делители;вместо a − kb можно взять остаток r0 от деления нацелоa на b : a = bq + r0 , q ∈ Z, 0 6 r0 < b;затем, переставив числа в паре, можно повторитьпроцедуру; она закончится, т.к.
числа в паре уменьшаются,но остаются неотрицательными.29 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхАлгоритм Евклида —— применяют для нахождения НОД(a, b) натуральных a и b.Наблюдение: общий делитель пары чисел (a, b), то остаётся ими для пары (a − b, b) (считаем, что a > b).Отсюда:пары чисел (a, b) и (a − kb, b) (q ∈ Z) имеет одинаковыеобщие делители;вместо a − kb можно взять остаток r0 от деления нацелоa на b : a = bq + r0 , q ∈ Z, 0 6 r0 < b;затем, переставив числа в паре, можно повторитьпроцедуру; она закончится, т.к. числа в паре уменьшаются,но остаются неотрицательными.В результате: за конечное число шагов образуется пара (rn , 0).Ясно, что НОД(a, b) = rn .29 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IВычисление элементов в конечных полях30 / 71Алгоритм Евклида: общая схема (a > b)НОД (a, b) =Шаг (−2): r−2 = a — полагаем для удобства;Шаг (−1): r−1 = b — полагаем для удобства;Шаг 0: r−2 = r−1 q0 + r0 — делим r−2 на r−1 , остаток r0 ;Шаг 1: r−1 = r0 q1 + r1 — делим r−1 на r0 , остаток r1 ;... всегда делим с остатком бо́льшее число наменьшее, оставляем меньшее (оно становитсябо́льшим) и остаток (он становится меньшим);Шаг n: rn−2 = rn−1 qn + rn — делим rn−2 на rn−1 ,остаток rn ;Шаг n + 1: rn−1 = rn qn+1 + 0 — деление нацело ⇒ останов.Всегда r−2 > r−1 > r0 > r1 > .
. . > rn > 1.= rn .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхАлгоритм Евклида: примерНОД (252, 105) =31 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных полях31 / 71Алгоритм Евклида: примерНОД (252, 105) =Шаг (−2): r−2 = 252;Шаг (−1): r−1 = 105⇒ (252, 105);Шаг 0: 252 = 105 · 2 + 42⇒ (105, 42);Шаг 1: 105 = 42 · 2 + 21⇒ (42, 21);Шаг 2: 42 = 21 · 2 + 0⇒ (21, 0).= 21.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IВычисление элементов в конечных полях31 / 71Алгоритм Евклида: примерНОД (252, 105) =Шаг (−2): r−2 = 252;Шаг (−1): r−1 = 105⇒ (252, 105);Шаг 0: 252 = 105 · 2 + 42⇒ (105, 42);Шаг 1: 105 = 42 · 2 + 21⇒ (42, 21);Шаг 2: 42 = 21 · 2 + 0⇒ (21, 0).= 21.НОД (a, b, c) = НОД (a, (НОД (b, c))ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхСоотношение БезуУтверждение (соотношение Безу)Для любых натуральных a, b и d = НОД (a, b) найдутся целыекоэффициенты Безу x, y такие, что d = ax + by.32 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IВычисление элементов в конечных поляхСоотношение БезуУтверждение (соотношение Безу)Для любых натуральных a, b и d = НОД (a, b) найдутся целыекоэффициенты Безу x, y такие, что d = ax + by.ДоказательствоРассматриваем алгоритм Евклида с конца к началу:d = rn = rn−2 − rn−1 qn , затем, подставляя сюда значениеrn−1 = rn−3 − rn−2 qn−1 , получаемd = −qn rn−3 + (1 + qn qn−1 )rn−2 = αrn−3 + βrn−2для некоторых α, β ∈ Z и т.д.32 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхСоотношение БезуУтверждение (соотношение Безу)Для любых натуральных a, b и d = НОД (a, b) найдутся целыекоэффициенты Безу x, y такие, что d = ax + by.ДоказательствоРассматриваем алгоритм Евклида с конца к началу:d = rn = rn−2 − rn−1 qn , затем, подставляя сюда значениеrn−1 = rn−3 − rn−2 qn−1 , получаемd = −qn rn−3 + (1 + qn qn−1 )rn−2 = αrn−3 + βrn−2для некоторых α, β ∈ Z и т.д.Для нахождения по паре чисел (a, b) их НОД и коэффициентовБезу применяют расширенный алгоритм Евклида.32 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных полях33 / 71Расширенный алгоритм Евклида —— повторяет схему (простого) алгоритма Евклида, в которомна каждом шаге:1дополнительно вычисляются xi и yi по формуламxi = xi−2 − qi xi−1 ,yi = yi−2 − qi yi−1 ,x−2 = y−1 = 1 ,2i = 0, 1, ...;x−1 = y−2 = 0 ;справедливо соотношениеri = ri−2 −qi ri−1 = (axi−2 +byi−2 )−qi (axi−1 +byi−1 ) == a(xi−2 − qi xi−1 ) + b(yi−2 − qi yi−1 ) = axi + byi .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных полях34 / 71Расширенный алгоритм Евклида: примерЗадача.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
