Конечные поля (часть 2) (1127161)
Текст из файла
ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIЧасть IКонечные поля (поля Галуа) II1 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIПоля вычетов по модулю простого числаРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Векторная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями2 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIВычисление элементов в конечных поляхРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Векторная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями3 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIВекторная алгебра над конечным полемРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Векторная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями4 / 86ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIКорни многочленов над конечным полемРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Векторная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями5 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементовРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Векторная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями6 / 86ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов7 / 86Вычисления в мультипликативной группе расширения поляПример (построение поляF42 )Поле F42 можно строить с помощью любого (пока не доказано!)из трех неприводимых над F2 многочленов 4-степени:x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Сделаем это, взяв многочлен f (x) = x4 + x + 1.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов7 / 86Вычисления в мультипликативной группе расширения поляПример (построение поляF42 )Поле F42 можно строить с помощью любого (пока не доказано!)из трех неприводимых над F2 многочленов 4-степени:x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Сделаем это, взяв многочлен f (x) = x4 + x + 1.Будем задавать элементы F42 наборами коэффициентовмногочлена-остатка при делении на f , записывая их в порядкевозрастания степеней.Порождающим является элемент α = x, который записываетсякак (0, 1, 0, 0).Вычислим степени α, сведя результаты в таблицу.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементовМультипликативная группа поляα4 = α + 18 / 86F42 ∼= F2 [x]/ x4 + x + 1степень αα=α2 =α3 =1 + α = α4 =α + α2 = α5 =α2 + α3 = α6 =3α + α + 1 = α3 + α4 = α7 =1 + α2 = α + 1 + α2 + α = α8 =α + α3 = α9 =22α + 1 + α = α + α4 = α10 =α + α2 + α3 = α11 =231 + α + α + α = α2 + α3 + α4 = α12 =1 + α2 + α3 = α + α2 + α3 + α4 = α13 =1 + α3 = α + α3 + α4 = α14 =1 = α + α4 = α15 =1(0,(0,(0,(1,(0,(0,(1,(1,(0,(1,(0,(1,(1,(1,(1,x1,0,0,1,1,0,1,0,1,1,1,1,0,0,0,x20,1,0,0,1,1,0,1,0,1,1,1,1,0,0,x30)0)1)0)0)1)1)0)1)0)1)1)1)1)0)ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементовМультипликативная группа поля9 / 86F42 ∼= F2 [x]/ x4 + x + 1 ...Имея такую таблицу, очень просто производить умножение.Пример: (x3 + x + 1) · (x2 + x + 1) = ?ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементовМультипликативная группа поля9 / 86F42 ∼= F2 [x]/ x4 + x + 1 ...Имея такую таблицу, очень просто производить умножение.Пример: (x3 + x + 1) · (x2 + x + 1) = ?1Перемножить, учитывая x4 = x + 1 — можно, но сложно...ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементовМультипликативная группа поля9 / 86F42 ∼= F2 [x]/ x4 + x + 1 ...Имея такую таблицу, очень просто производить умножение.Пример: (x3 + x + 1) · (x2 + x + 1) = ?1Перемножить, учитывая x4 = x + 1 — можно, но сложно...2С помощью таблицы:представляем многочлены в векторной форме и по ней — ввиде степеней α:x3 + x + 1 ↔ (1, 1, 0, 1) ↔ α7 ,x2 + x + 1 ↔ (1, 1, 1, 0) ↔ α10перемножая, c учётом α15 = 1, получаем:α7 α10 = α17 = α2 = x2 .Таким образом: (x3 + x + 1) · (x2 + x + 1) = x2 .ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов10 / 86Пути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp(везде p — простое, n — натуральное).ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов10 / 86Пути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp(везде p — простое, n — натуральное).Это можно сделать двумя способами.а) ⇒ б) доказать существование поля из pn элементов,откуда вывести существование неприводимогомногочлена степени n над Fp ;б) ⇒ а) установить существование неприводимогомногочлена f степени n над Fp , откуда ужеследует существование поля из pn какфактор-кольца по идеалу (f ).Мы пойдём вторым путём.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов11 / 86Существование неприводимого многочленаДокажем существование нормированного неприводимогомногочлена в полях Галуа.Для таких многочленов выполняется аналог основной теоремыарифметики: каждый нормированный многочлен однозначноразлагается на произведение степеней неприводимыхмногочленов.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов11 / 86Существование неприводимого многочленаДокажем существование нормированного неприводимогомногочлена в полях Галуа.Для таких многочленов выполняется аналог основной теоремыарифметики: каждый нормированный многочлен однозначноразлагается на произведение степеней неприводимыхмногочленов.Действительно:разложение в евклидовом кольце однозначно (с точностьюдо умножения на обратимые элементы — делители);в случае кольца многочленов над полем обратимыеэлементы — ненулевые константы (многочлены степени 0);выбор старшего коэффициента 1 однозначно определяетсомножители.ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов12 / 86Количество неприводимых нормированных многочленовЛемма (о величине dn )Если dn — число неприводимых нормированных многочленовстепени n над Fp , то Pm · dm = pn .m|nПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов12 / 86Количество неприводимых нормированных многочленовЛемма (о величине dn )Если dn — число неприводимых нормированных многочленовстепени n над Fp , то Pm · dm = pn .m|nДоказательствоЗанумеруем i = 1, .
. . , dn все неприводимые нормированныемногочлены степени n и сопоставим им формальнуюпеременную fi,n ⇒ произвольному такому многочленуоднозначно сопоставлен моном (многочлен степени nj берётсяв степени sj ):rPfis11,n1 · . . . · fisrr,nr , причемnj sj = n.j=1ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов13 / 86Количество неприводимых нормированных многочленов...Доказательство (продолжение)Поэтому все нормированные многочлены перечисляютсяформальным бесконечным произведением!∞Y XXkfi,n =fis11,n1 · .
. . · fisrr,nri,n(∗)k=0(раскрыты скобки и бесконечное произведение записано в видеформального ряда).Сделаем замену переменных fi,n = tn , которая делает всемногочлены одной степени неразличимыми.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов14 / 86Количество неприводимых нормированных многочленов...Доказательство (продолжение)!∞Y XXkfi,n=fis11,n1 · . . . · fisrr,nri,nk=0Приведение подобных приведёт к тому, что:в правой части (∗) будет ряд от переменной t.Коэффициент при tn в этом ряде равен числунормированных многочленов степени n, т.е. pn :∞Xn=0pn tn .(∗)ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля (поля Галуа) IIСуществование и единственность поля Галуа из pn элементов15 / 86Количество неприводимых нормированных многочленов...Доказательство (продолжение)!∞∞Y XXkfi,n =pn tni,n(∗)n=0k=0в левой части все неприводимые многочлены степени nдадут одинаковый множитель (сумму бесконечнойгеометрической прогрессии со знаменателем tn ) и(∗) превращается в∞Y Xnk=0!dnnkt=∞Xn=0pn tn .ПРИКЛАДНАЯ АЛГЕБРА.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
