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

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

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

. . , p − 1}, +mod p , ·modp i.Fp [x] многочленов над ним.2Образуем кольцо3Выбираем натуральное n и неприводимый многочлен n-йстепени P (x) = an xn + . . . + a1 x + a0 ∈ Fp [x].4Идеал (P (x)) порождает фактормножество Fp [x]/(P (x)),элементы которого суть совокупность {R(x)} остатков отделения многочленов f ∈ Fp [x] на P (x):f (x) = Q(x) · P (x) + R(x) .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа23 / 160Построение конечных полей— с использованием неприводимых многочленов.1Выбираем простое p и фиксируем полеFp = h{ 0̄, 1̄, . . .

, p − 1}, +mod p , ·modp i.Fp [x] многочленов над ним.2Образуем кольцо3Выбираем натуральное n и неприводимый многочлен n-йстепени P (x) = an xn + . . . + a1 x + a0 ∈ Fp [x].4Идеал (P (x)) порождает фактормножество Fp [x]/(P (x)),элементы которого суть совокупность {R(x)} остатков отделения многочленов f ∈ Fp [x] на P (x):f (x) = Q(x) · P (x) + R(x) .УтверждениеМножество {R(x)} является полем Галуа GF (pn ).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение конечных полей...Доказательство12кольцо многочленов Fp [x] евклидово, идеал (P (x)) —максимальный ⇒ {R(x)} — поле;|{R(x)}| = число многочленов над Fp степени не вышеn − 1, т.е. |{R(x)}| = pn .24 / 160Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 160Построение конечных полей...Доказательство12кольцо многочленов Fp [x] евклидово, идеал (P (x)) —максимальный ⇒ {R(x)} — поле;|{R(x)}| = число многочленов над Fp степени не вышеn − 1, т.е.

|{R(x)}| = pn .Поле Галуа {R(x)} называетсярасширением n-й степени поляFp и обозначается Fnp .ВопросПочему в обозначении Fnp не используется многочлен P (x), спомощью которого построено поле?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа24 / 160Построение конечных полей...Доказательство12кольцо многочленов Fp [x] евклидово, идеал (P (x)) —максимальный ⇒ {R(x)} — поле;|{R(x)}| = число многочленов над Fp степени не вышеn − 1, т.е. |{R(x)}| = pn .Поле Галуа {R(x)} называетсярасширением n-й степени поляFp и обозначается Fnp .ВопросПочему в обозначении Fnp не используется многочлен P (x), спомощью которого построено поле?ТеоремаЛюбое конечное поле изоморфно какому-нибудь полю ГалуаFnp .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПример: построение поля25 / 160F23Выберем неприводимый многочлен вИскомое поле есть F23 ==F3 [x]/(x2 + 1)F3 [x] :x2 + 1.= { 0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2 }.Можно составить таблицу сложения и умножения в этом поле.Например (применяем обычные правила с учётом x2 ≡3 2):(x + 1) + (x + 2) = 2x,(2x + 1) + (x) = 1,(x) · (2x) = 1,(2x + 1) · (x) = x + 1.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля26 / 160F23 ...Заметим, что(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Это значит, что α = x + 1 — примитивный элементмультипликативной группы F2∗3 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля26 / 160F23 ...Заметим, что(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Это значит, что α = x + 1 — примитивный элементмультипликативной группы F2∗3 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в F3 [x] многочлен? Например,2x2 + x + 1?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля26 / 160F23 ...Заметим, что(x + 1)1 = x + 1,(x + 1)5 = 2x + 2,(x + 1)2 = 2x,(x + 1)6 = x,(x + 1)3 = 2x + 1,(x + 1)7 = x + 2,(x + 1)4 = 2,(x + 1)8 = 1.Это значит, что α = x + 1 — примитивный элементмультипликативной группы F2∗3 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в F3 [x] многочлен? Например,2x2 + x + 1?Ответ: получится поле, изоморфное построенному.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды27 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел IIКоды БЧХЧто надо знать28 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях29 / 160Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)— он понадобится для вычислений в конечных полях.Наблюдение: если d — общий делитель пары чисел (a, b) ⇔d — общий делитель чисел (a − b, b).Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях29 / 160Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)— он понадобится для вычислений в конечных полях.Наблюдение: если d — общий делитель пары чисел (a, b) ⇔d — общий делитель чисел (a − b, b).Отсюда:пары чисел (a, b) (a − kb, b), k ∈ Z имеет одинаковыеобщие делители;Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях29 / 160Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)— он понадобится для вычислений в конечных полях.Наблюдение: если d — общий делитель пары чисел (a, b) ⇔d — общий делитель чисел (a − b, b).Отсюда:пары чисел (a, b) (a − kb, b), k ∈ Z имеет одинаковыеобщие делители;вместо a − kb можно взять остаток r0 от деления нацело aна b: a = bq + r0 , q ∈ Z, 0 6 r0 < b;Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях29 / 160Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)— он понадобится для вычислений в конечных полях.Наблюдение: если d — общий делитель пары чисел (a, b) ⇔d — общий делитель чисел (a − b, b).Отсюда:пары чисел (a, b) (a − kb, b), k ∈ Z имеет одинаковыеобщие делители;вместо a − kb можно взять остаток r0 от деления нацело aна b: a = bq + r0 , q ∈ Z, 0 6 r0 < b;затем, переставив числа в паре, можно повторитьпроцедуру; она закончится, т.к.

числа в паре уменьшаются,но остаются неотрицательными.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях29 / 160Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)— он понадобится для вычислений в конечных полях.Наблюдение: если d — общий делитель пары чисел (a, b) ⇔d — общий делитель чисел (a − b, b).Отсюда:пары чисел (a, b) (a − kb, b), k ∈ Z имеет одинаковыеобщие делители;вместо a − kb можно взять остаток r0 от деления нацело aна b: a = bq + r0 , q ∈ Z, 0 6 r0 < b;затем, переставив числа в паре, можно повторитьпроцедуру; она закончится, т.к.

числа в паре уменьшаются,но остаются неотрицательными.В результате за конечное число шагов образуется пара (rn , 0).Ясно, что НОД(a, b) = rn .Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхАлгоритм Евклида: общая схемаНОД(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.НОД(a, b) = rn .30 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхАлгоритм Евклида: примерНОД(252, 105) =?31 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях31 / 160Алгоритм Евклида: примерНОД(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).НОД(252, 105) = 21.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях31 / 160Алгоритм Евклида: примерНОД(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).НОД(252, 105) = 21.НОД(a, b, c) = НОД(a, (НОД(b, c))Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхТеорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если d = НОД(a, b), то найдутся x, y ∈ Z такие, что d = ax + by.32 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхТеорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если d = НОД(a, b), то найдутся x, y ∈ Z такие, что 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 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхТеорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если d = НОД(a, b), то найдутся x, y ∈ Z такие, что 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) натурального dи целых x и y таких, чтоd = НОД(a, b) = ax + ay,применяют расширенный алгоритм Евклида.32 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 160Расширенный алгоритм ЕвклидаРасширенный алгоритм Евклида повторяет схему (простого)алгоритма Евклида, при в котором на каждом шаге:дополнительно вычисляются xi и yi по формуламxi = xi−2 − qi xi−1 ,yi = yi−2 − qi yi−1 ,i = 0, 1, ...;x−2 = y−1 = 1 .справедливо соотношение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 .Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях34 / 160Расширенный алгоритм Евклида: примерЗадача: найти натуральное d и целые x и y таких, чтоd = НОД(a, b) = 252x + 105y.Решение: имеем xi = xi−2 − qi xi−1 ,Сведём все вычисления в таблицу:шаг i-2-1012ri−2ri−1qi252105421054221222Ответ: d = 21, x = −2, y = 5.yi = yi−2 − qi yi−1 .ri25210542210xi101-2yi01-25Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 160ЗадачаВ поле Z/(101) решить уравнение4x = 1.(∗)Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 160ЗадачаВ поле Z/(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 102, 203, 304, .

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

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