AA3-1(GF-I) (1127138)
Текст из файла
ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЧасть IКонечные поля или поля Галуа.I1 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать2 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПоле GF (p)Z — кольцо целых чисел евклидово (целостное унитальное +возможно деление с остатком ⇒ существование НОД!),p — простое число.(p) = { np | n ∈ Z } = pZ = { 0, ±p, ±2p, .
. . } — идеалZ/(p) = 0, 1, . . . , p − 1 — кольцо вычетов по модулюэтого идеала = классы остатков от деления на p:0= 0 + pZ ,1= 1 + pZ ,⇒ Z = 0 ∪ 1 ∪ . . . ∪ p − 1.········· Черту над символами классовp − 1 = (p − 1) + pZ .вычетов часто не ставят.3 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПоле GF (p)Z — кольцо целых чисел евклидово (целостное унитальное +возможно деление с остатком ⇒ существование НОД!),p — простое число.(p) = { np | n ∈ Z } = pZ = { 0, ±p, ±2p, .
. . } — идеалZ/(p) = 0, 1, . . . , p − 1 — кольцо вычетов по модулюэтого идеала = классы остатков от деления на p:0= 0 + pZ ,1= 1 + pZ ,⇒ Z = 0 ∪ 1 ∪ . . . ∪ p − 1.········· Черту над символами классовp − 1 = (p − 1) + pZ .вычетов часто не ставят.Поскольку p — простое, то Z/(p) — не просто кольцо, а поле(возможно деление без остатка на любой ненулевой элемент).Это простейшее поле Галуа, обозначение — Fp или GF (p); всеоперации в нём — по mod p.3 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПолеF3 :4 / 71F3 = Z/(3) и факторкольцо Z/(4)+012001211202201×012000010122021ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПоле4 / 71F3 = Z/(3) и факторкольцо Z/(4)F3 :+012001211202201Z/(4) :+012300123112302230133012×012000010122021×012300000101232020230321Дважды два равно нулю!ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаПоле4 / 71F3 = Z/(3) и факторкольцо Z/(4)F3 :+012001211202201Z/(4) :+012300123112302230133012×012000010122021×012300000101232020230321Дважды два равно нулю!Однако, поле из 4-х элементов существует...ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаХарактеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , . . ..5 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа5 / 71Характеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , .
. .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. . + 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdefПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа5 / 71Характеристика поляПусть k — произвольное поле, 1 — единица k.
Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. . + 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdef{ 0, 1, 2, . . . , char k − 1 } — минимальное подполе в поле k.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа5 / 71Характеристика поляПусть k — произвольное поле, 1 — единица k. Складываем их:1 = 1 , 2 = 1 + 1 , . . .. В конечном поле всегда найдётсяпервое k такое, что 1| + .{z. . + 1} = 0. Тогдаk разk = порядок аддитивной группы поля k == характеристика поля k = char kdef{ 0, 1, 2, . . . , char k − 1 } — минимальное подполе в поле k.Если все суммы вида 1 + . . . + 1 различны, то char k = 0.Примеры: Q, R — поля нулевой (или бесконечной :))характеристики.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикой6 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле. Построим:1k[x] — кольцо многочленов от формальной переменной x:{ P (x) = a0 + a1 x + . . . + an xn }, a0 , . . .
, an ∈ k,n ∈ N, an 6= 0; k[x] ↔ {(a0 , . . . , an ) ∈ kn | n ∈ N}.6 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле. Построим:12k[x] — кольцо многочленов от формальной переменной x:{ P (x) = a0 + a1 x + . . . + an xn }, a0 , . . . , an ∈ k,n ∈ N, an 6= 0; k[x] ↔ {(a0 , . . . , an ) ∈ kn | n ∈ N}.k(x) — поле рациональных функций над k6 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаБесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле.
Построим:12k[x] — кольцо многочленов от формальной переменной x:{ P (x) = a0 + a1 x + . . . + an xn }, a0 , . . . , an ∈ k,n ∈ N, an 6= 0; k[x] ↔ {(a0 , . . . , an ) ∈ kn | n ∈ N}.k(x) — поле рациональных функций над k; в нём:элементы — “дроби” P/Q (если Q 6= 0), где P, Q ∈ k[x];умножение — (P/Q) · (U/V ) = (P U )/(QV );эквивалентность — P1 /Q1 = P2 /Q2 , если P1 Q2 = P2 Q1 ;сложение — дроби можно приводить к общемузнаменателю и складывать:P/Q + U/V = (P V )/(QV ) + (QU )/(QV ) = (P V + QU )/(QV );включение — Поскольку k[x] ⊂ k(x), то каждый многочленP отождествляется с P/1.6 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числа6 / 71Бесконечное поле с положительной характеристикойk — произвольное (конечное или бесконечное) поле. Построим:12k[x] — кольцо многочленов от формальной переменной x:{ P (x) = a0 + a1 x + . . . + an xn }, a0 , . . . , an ∈ k,n ∈ N, an 6= 0; k[x] ↔ {(a0 , .
. . , an ) ∈ kn | n ∈ N}.k(x) — поле рациональных функций над k; в нём:элементы — “дроби” P/Q (если Q 6= 0), где P, Q ∈ k[x];умножение — (P/Q) · (U/V ) = (P U )/(QV );эквивалентность — P1 /Q1 = P2 /Q2 , если P1 Q2 = P2 Q1 ;сложение — дроби можно приводить к общемузнаменателю и складывать:P/Q + U/V = (P V )/(QV ) + (QU )/(QV ) = (P V + QU )/(QV );включение — Поскольку k[x] ⊂ k(x), то каждый многочленP отождествляется с P/1.Если в качестве k взять конечное поле Fp , тополе положительной характеристики p.Fp (x) — бесконечноеПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаСильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .7 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа7 / 71Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap−1 b + .
. . + Cpp−1 abp−1 + bp .Но при i = 1, . . . , p − 1 числитель коэффициента Cpi =делится на p, а знаменатель — нет, ∴ Cpi ≡p 0.p!i!(p−i)!ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа7 / 71Сильное упрощение вычислений в поле положительнойхарактеристикиЛеммаВ поле характеристики p > 0 выполнено тождество(a + b)p = ap + bp .ДоказательствоВ любом коммутативном кольце верна формула для бинома(a + b)p = ap + Cp1 ap−1 b + . .
. + Cpp−1 abp−1 + bp .Но при i = 1, . . . , p − 1 числитель коэффициента Cpi =делится на p, а знаменатель — нет, ∴ Cpi ≡p 0.p!i!(p−i)!СледствиеnnnВ поле характеристики p > 0 справедливо (a + b)p = ap + bp .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .8 / 71FpПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IПоля вычетов по модулю простого числаМультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .УтверждениеF∗p — циклическая группа порядка p − 1 по умножению.8 / 71FpПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа8 / 71Мультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .УтверждениеF∗p — циклическая группа порядка p − 1 по умножению.Как любая конечная циклическая группа,генератор = примитивный элемент α:F∗p содержитлюбой элемент β ∈ F∗p является некоторой егонатуральной степенью: β = αi , i ∈ { 1, .
. . , p − 1};причём 1 = αp−1 — т.е. αi 6= 1 для 1 6 i 6 p − 2.FpПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числа8 / 71Мультипликативная группа и примитивный элемент поляF∗pdef=Fp r {0} — мультипликативная группа поля Fp .УтверждениеF∗p — циклическая группа порядка p − 1 по умножению.Как любая конечная циклическая группа,генератор = примитивный элемент α:F∗p содержитлюбой элемент β ∈ F∗p является некоторой егонатуральной степенью: β = αi , i ∈ { 1, . . . , p − 1};причём 1 = αp−1 — т.е.
αi 6= 1 для 1 6 i 6 p − 2.УтверждениеГруппаF∗pимеет ϕ(p − 1) примитивных элементов.FpПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера — количество чисел из интервала[ 1, . . . , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = {1, 5} = 2, . .
.9 / 71ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IПоля вычетов по модулю простого числаФункция Эйлераϕ(n) — функция Эйлера — количество чисел из интервала[ 1, . . . , n − 1 ], взаимно простых с n:ϕ(1) = 1 (по определению), ϕ(2) = 1, ϕ(3) = ϕ(4) = 2,ϕ(5) = 4, ϕ(6) = {1, 5} = 2, . . .Свойства (p — простое число):ϕ(n) 6 n − 1 и ϕ(p) = p − 1;ϕ(nm ) = nm−1 ϕ(n), т.е. ϕ(pm ) = pm−1 (p − 1);d, где d = НОД(m, n),ϕ(mn) = ϕ(m)ϕ(n) ϕ(d)откуда: если m и n взаимно просты, тоϕ(mn) = ϕ(m)ϕ(n) ( ϕ(·) — мультпликативная функция).Пример: ϕ(15) = ϕ(3 · 5) = ϕ(3)ϕ(5) = (3 − 1)(5 − 1) = 8,ϕ(16) = ϕ(24 ) = 23 · ϕ(2) = 8.9 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
