Лекции по прикладной алгебре. v2.0 (1127112), страница 3

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

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

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

. , p − 1}, +mod p , ·mod p .2Образуем кольцо3Выбираем натуральное n и неприводимый многочленP (x) = an xn + . . . + a1 x + a0 ∈ Fp [x].4Fp [x] многочленов над ним.Идеал (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 ).25 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение конечных полей...Доказательство12кольцо многочленов Fp [x] евклидово, идеал (P (x)) —⇒ {R(x)} — поле;максимальный{R(x)} = число многочленов над Fp степени не вышеn − 1, т.е.

{R(x)} = pn .26 / 432Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа26 / 432Построение конечных полей...Доказательство12кольцо многочленов Fp [x] евклидово, идеал (P (x)) —⇒ {R(x)} — поле;максимальный{R(x)} = число многочленов над Fp степени не вышеn − 1, т.е.

{R(x)} = pn .Поле Галуа {R(x)} называетсярасширением n-й степени поляFp и обозначается Fnp .ВопросПочему в обозначении Fnp не используется многочлен P (x), спомощью которого построено поле?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числа26 / 432Построение конечных полей...Доказательство12кольцо многочленов Fp [x] евклидово, идеал (P (x)) —⇒ {R(x)} — поле;максимальный{R(x)} = число многочленов над Fp степени не вышеn − 1, т.е. {R(x)} = pn .Поле Галуа {R(x)} называетсярасширением n-й степени поляFp и обозначается Fnp .ВопросПочему в обозначении Fnp не используется многочлен P (x), спомощью которого построено поле?ТеоремаЛюбое конечное поле изоморфно какому-нибудь полю ГалуаFnp .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПример: построение поля27 / 432F23Выберем неприводимый многочлен вИскомое поле естьF23∼=F3 [x]/(x2 + 1)=F3 [x] :x2 + 1.=0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2Можно составить таблицу сложения и умножения в этом поле сучётом x2 = −1 ≡3 2.Например:(x + 1) + (x + 2) = 2x,(2x + 1) + (x) = 1,и т.д.(x) · (2x) = 1,(2x + 1) · (x) = x + 1,Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 432F23 ...Заметим, что, например,(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.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 432F23 ...Заметим, что, например,(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 — примитивный элемент (генератор)мультипликативной группы поля F23 .Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 432F23 ...Заметим, что, например,(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 — примитивный элемент (генератор)мультипликативной группы поля F23 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в F3 [x] многочлен?Например, 2x2 + x + 1?Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаПостроение поля28 / 432F23 ...Заметим, что, например,(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 — примитивный элемент (генератор)мультипликативной группы поля F23 .ВопросЧто будет, если при построении поля вместо x2 + 1 взятьдругой неприводимый в F3 [x] многочлен?Например, 2x2 + x + 1?Ответ: получится поле, изоморфное построенному.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаЧисло неприводимых многочленов в поле29 / 432FnpНеприводимый многочлен f (x) — в поле Fnp — примитивныйэлемент мультипликативной группы Fpn∗ , т.е.pn −1i1f (x)= 1 и f (x) 6= 1 для 0 < i < pn − 1,2для любого многочлена g(x) ∈ Fn∗p найдётся степень iiтакая, что g(x) = f (x) , i ∈ { 0, 1, .

. . , pn − 1 }.Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаЧисло неприводимых многочленов в поле29 / 432FnpНеприводимый многочлен f (x) — в поле Fnp — примитивныйэлемент мультипликативной группы Fpn∗ , т.е.pn −1i1f (x)= 1 и f (x) 6= 1 для 0 < i < pn − 1,2для любого многочлена g(x) ∈ Fn∗p найдётся степень iiтакая, что g(x) = f (x) , i ∈ { 0, 1, . . . , pn − 1 }.Если α — примитивный элемент поля GF (q), то любой другойпримитивный элемент может быть получен как степень αk , гдеk — целое число взаимно простое с q − 1 ⇒ количестворазличных примитивных элементов в поле Fnp равно ϕ(pn − 1).Прикладная алгебраПоля ГалуаПоля вычетов по модулю простого числаЧисло неприводимых многочленов в поле29 / 432FnpНеприводимый многочлен f (x) — в поле Fnp — примитивныйэлемент мультипликативной группы Fpn∗ , т.е.pn −1i1f (x)= 1 и f (x) 6= 1 для 0 < i < pn − 1,2для любого многочлена g(x) ∈ Fn∗p найдётся степень iiтакая, что g(x) = f (x) , i ∈ { 0, 1, .

. . , pn − 1 }.Если α — примитивный элемент поля GF (q), то любой другойпримитивный элемент может быть получен как степень αk , гдеk — целое число взаимно простое с q − 1 ⇒ количестворазличных примитивных элементов в поле Fnp равно ϕ(pn − 1).Например, в полеF62 из 64 элементовϕ(63) = ϕ(32 · 7) = 31 · 2 · 6 = 36примитивных элементов = неприводимых многочленов.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.

Коды ХэммингаГрупповые (линейные) коды30 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств31 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.

множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать32 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)— он понадобится для вычислений в конечных полях.Наблюдение: если d — общий делитель пары чисел (a, b), то dостаётся общим делителем для чисел (a − b, b).Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(a, b) натуральныхчисел a и b (a > b)— он понадобится для вычислений в конечных полях.Наблюдение: если d — общий делитель пары чисел (a, b), то dостаётся общим делителем для чисел (a − b, b).Отсюда:пары чисел (a, b) и (a − kb, b) (k ∈ Z) имеет одинаковыеобщие делители;Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(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;Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(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;затем, переставив числа в паре, можно повторитьпроцедуру; она закончится, т.к.

числа в паре уменьшаются,но остаются неотрицательными.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях33 / 432Алгоритм Евклида для нахождения НОД(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)НОД(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 .34 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхАлгоритм Евклида: примерНОД(252, 105) =?35 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 432Алгоритм Евклида: примерНОД(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.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 432Алгоритм Евклида: примерНОД(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.36 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхТеорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если 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 и т.д.36 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхТеорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если 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,применяют расширенный алгоритм Евклида.36 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях37 / 432Расширенный алгоритм ЕвклидаРасширенный алгоритм Евклида повторяет схему (простого)алгоритма Евклида, в котором на каждом шаге:дополнительно вычисляются 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 .Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях38 / 432Расширенный алгоритм Евклида: примерЗадача.

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

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