Конечные поля (часть 2) (1127161), страница 3
Текст из файла (страница 3)
. . , an−1 ) | ai ∈ F, i = 0, 1, . . . , n − 1 } —координатное пространство.ОпределениеПодпространство координатного пространства F n называетсяциклическим, если вместе с набором (a0 , . . . , an−1 ) оносодержит циклический сдвиг (вправо) этого набора, т.е. набор(an−1 , a0 , . . . , an−2 ) (а следовательно и все циклическиесдвиги на произвольное число позиций влево и вправо).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства29 / 86Кольцо классов вычетов по модулю многочлена xn − 1Fp [x]/(xn − 1), рассматриваемом nкак векторное oпространство над полем Fp имеется базис 1, x, . .
. , xn−1 .В кольцеЦиклический сдвиг координат в этом базисе равносиленумножению на x:(a0 + a1 x + . . . + an−2 xn−2 + an−1 xn−1 ) · x == (a0 x + a1 x2 + . . . + an−2 xn−1 + an−1 xn ) == (an−1 + a0 x + a1 x2 + . . . + an−2 xn−1 ),т.к. в этом кольце xn = 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваИдеал вFp [x]/(xn − 1) — циклическое пространствоТеоремаПусть I — подпространство кольца Fp [x]/(xn − 1).Тогда I — циклическое ⇔ I C Fp /(xn − 1).30 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваИдеал вFp [x]/(xn − 1) — циклическое пространствоТеоремаПусть I — подпространство кольца Fp [x]/(xn − 1).Тогда I — циклическое ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг ⇒ I — циклическое.30 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваИдеал в30 / 86Fp [x]/(xn − 1) — циклическое пространствоТеоремаПусть I — подпространство кольца Fp [x]/(xn − 1).Тогда I — циклическое ⇔ I C Fp /(xn − 1).ДоказательствоЕсли подпространство I — идеал, то оно замкнутоотносительно умножения на x, а это умножение и естьциклический сдвиг ⇒ I — циклическое.Пусть I — циклическое подпространство кольцаFp /(xn − 1) и g ∈ I.Тогда g · x, g · x2 , . . . — циклические сдвиги, т.е. такжепринадлежат I.Значит, g · f ∈ I для любого многочлена f , поэтому I —идеал.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваПримитивные корниБыло показано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором полеFq = Fnp характеристики p ( q = pn ).Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1.31 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства31 / 86Примитивные корниБыло показано: любой многочлен с коэффициентами из Fpразлагается на линейные множители в некотором полеFq = Fnp характеристики p ( q = pn ).Пусть Fq — поле характеристики p, в котором разлагаетсямногочлен xn − 1. Справедливо:В Fq выполняется равенство xkp − 1 = (xk − 1)p , поэтомуинтересен случай, когда n взаимно просто с p: тогда умногочлена xn − 1 кратных корней нет (он взаимно простсо своей производной nxn−1 ).Равенство xn = 1 означает, что порядок элемента xв мультипликативной циклической группе F∗q делит n.Вывод: корни уравнения xn − 1 = 0 образуют группу корнейстепени n из единицы — подгруппу в F∗q .Эта подгруппа также циклическая; её порождающие элементыназываются примитивными корнями степени n.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства32 / 86Количество и степени неприводимых делителей xn − 1Подгруппа в циклической группе существует iff её порядокделит порядок циклической группы ⇒ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространства32 / 86Количество и степени неприводимых делителей 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.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваРазложение многочлена x15 − 1 над полем33 / 86F2ПримерРассмотрим ещё раз разложение многочлена 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 над полем34 / 86F2ПримерРассмотрим разложение многочлена 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Циклические подпространстваКольца многочленов35 / 86Fp [x] и конечные поля: резюмеЛюбая конечное целостностное кольцо является полем.Характеристика конечного поля — простое число.Любое конечное поле характеристики p состоит из q = pnэлементов n ∈ N.Мультипликативный порядок любого ненулевого элементаполя GF (q) делит q − 1.Мультипликативная группа поля GF (q) являетсяциклической: в ней существует элемент порядка q − 1(генератор); конкретнее — ϕ(q − 1) генераторов.Для нахождения самих генераторов нет эффективныхалгоритмов.Любые два конечных поля, содержащих одинаковоеколичество элементов, изоморфны.GF (pm ) ⊆ GF (pn ) ⇔ m | n.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваКольца многочленов36 / 86Fp [x] и конечные поля: резюме...Неформально векторное пространство над полем —множество, устойчивое относительно сложения, вычитанияи умножения на элементы поля с естественнымиаксиомами сложения и умножения.Одночлены 1, x, x2 , .
. . — базис в бесконечномерномвекторном пространстве над полем коэффициентов.Для каждого натурального n в кольце многочленов Fp [x]над простым полем Fp имеются неприводимые (неимеющие несобственных делителей) многочлены.Кольцо Fp [x] — кольцо с однозначным разложениеммногочленов на неприводимые. Количество неприводимыхмногочленов вычисляется через функцию Мёбиуса, длянахождения самих неприводимых многочленов нетэффективных алгоритмов (пользуются таблицами).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваКольца многочленов37 / 86Fp [x] и конечные поля: резюме...Идеал (a(x)), порождённый многочленом a(x) ∈ Fp [x]составляют многочлены, кратные a(x).Фактор-кольцо Fp [x]/(a(x)) является полем, если и толькоесли a(x) — неприводимый многочлен в кольце Fp [x].Если при этом deg a(x) = n, то элементы Fp [x]/(a(x)) —многочлены степени < n ( pn элементов).Минимальный многочлен элемента β расширенного поляесть нормированный многочлен минимальной степени, длякоторого β является корнем.
Минимальные многочленынеприводимы и единственны для каждого β.Любой элемент поля F = Fnp является корнемnмногочлена xp − x:Qnxp − x =(x − a).a∈FПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЦиклические подпространстваКольца многочленов38 / 86Fp [x] и конечные поля: резюме...Для того, чтобы векторное подпространство V кольцаR = Fp [x](xn − 1) было циклическим кодом, необходимои достаточно, чтобы оно было идеалом R.Многочлен g(x) порождает идеал R, если он являетсяделителем xn − 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Векторная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями39 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-1 (теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.40 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-1 (теорема Вильсона)Доказать, что (p − 1)! ≡p −1 для простого p.Решениеp = 2: — утверждение тривиально.40 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями40 / 86Задача ПГ-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.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-1...Ещё одноРешение: очевидно, если в Fp обозначимP = 1 · 2 · . . . · (p − 1), то получимP 2 = ( 1 · 2 · . . . · (p − 1) ) · ( 1 · 2 · . . . · (p − 1) ) = 1,поскольку для каждого элемента в первой скобке найдётсяединственный обратный ему элемент во второй.В Fp имеется лишь два элемента обратных самим себе: 1 иp − 1.Поскольку P 6= 1, то P = p − 1 и P + 1 делится на p.41 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЗадачи с решениямиЗадача ПГ-2Найти x ≡17 12006 + 22006 + . . . + 162006 .42 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями42 / 86Задача ПГ-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-х элементов.43 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIЗадачи с решениями43 / 86Задача ПГ-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Задачи с решениями44 / 86Задача ПГ-4Производная многочлена f 6= 0 над полем характеристики pтождественно равна 0.Доказать, что этот многочлен приводимый.ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
