AA3-1(GF-II) (PDF-лекции от Гурова)

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIЧасть IКонечные поля или поля Галуа.II1 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIПоля вычетов по модулю простого числаРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать2 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.

IIВычисление элементов в конечных поляхРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать3 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.

IIЛинейная алгебра над конечным полемРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать4 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIКорни многочленов над конечным полемРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать5 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементовРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать6 / 78ПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов7 / 78Вычисления в мультипликативной группе расширения поляНачнём с примера поляF42 .ПримерПоле F42 можно строить с помощью любого из трехнеприводимых над F2 многочленов (но пока не доказано):x4 + x + 1,x4 + x3 + 1,x 4 + x3 + x2 + x + 1Сделаем это, взяв многочлен f (x) = x4 + x + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.

IIСуществование и единственность поля Галуа из pn элементов7 / 78Вычисления в мультипликативной группе расширения поляНачнём с примера поляF42 .ПримерПоле F42 можно строить с помощью любого из трехнеприводимых над F2 многочленов (но пока не доказано):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 / 78F42 ∼= 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 / 78F42 ∼= F2 [x]/ x4 + x + 1 ...Имея такую таблицу, очень просто производить умножение.Пример: (x3 + x + 1) · (x2 + x + 1) = ?ПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементовМультипликативная группа поля9 / 78F42 ∼= F2 [x]/ x4 + x + 1 ...Имея такую таблицу, очень просто производить умножение.Пример: (x3 + x + 1) · (x2 + x + 1) = ?1Перемножить, учитывая x4 = x + 1 — можно, но сложно...ПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементовМультипликативная группа поля9 / 78F42 ∼= F2 [x]/ x4 + x + 1 ...Имея такую таблицу, очень просто производить умножение.Пример: (x3 + x + 1) · (x2 + x + 1) = ?1Перемножить, учитывая x4 = x + 1 — можно, но сложно...2С помощью таблицы:представляем многочлены в векторной форме и по ней — ввиде степеней α = x:x3 + x + 1 ↔ (1, 1, 0, 1) ↔ α7 ,x2 + x + 1 ↔ (1, 1, 1, 0) ↔ α10перемножая, получаем: α7 α10 = α17 = α2 = x2 .Таким образом: (x3 + x + 1) · (x2 + x + 1) = x2 .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp(везде p — простое, n — натуральное).10 / 78ПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементовПути доказательстваТеперь можно вернуться к вопросу о существованииа) конечного поля Fq размера q, показав, что всегдаq = pn ;б) неприводимого многочлена степени n над Fp(везде p — простое, n — натуральное).Это можно сделать двумя способами.а) ⇒ б) доказать существование поля из pn элементов,откуда вывести существование неприводимогомногочлена степени n над Fp ;б) ⇒ а) установить существование неприводимогомногочлена f степени n над Fp , откуда ужеследует существование поля из pn какфакторкольца по идеалу (f ).Мы пойдём вторым путём.10 / 78ПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов11 / 78Существование неприводимого многочленаДокажем существование нормированного неприводимогомногочлена в полях Галуа.Для таких многочленов выполняется аналог основной теоремыарифметики: каждый нормированный многочлен однозначноразлагается на произведение степеней неприводимыхмногочленов.ПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов11 / 78Существование неприводимого многочленаДокажем существование нормированного неприводимогомногочлена в полях Галуа.Для таких многочленов выполняется аналог основной теоремыарифметики: каждый нормированный многочлен однозначноразлагается на произведение степеней неприводимыхмногочленов.Действительно:разложение в евклидовом кольце однозначно (с точностьюдо умножения на обратимые элементы — делители);в случае кольца многочленов над полем обратимыеэлементы — ненулевые константы (многочлены степени 0);выбор старшего коэффициента 1 однозначно определяетсомножители.ПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементовКоличество неприводимых нормированных многочленовЛемма (о числе dn )Если dn — число неприводимых нормированных многочленовстепени n над Fp , то Pm · dm = pn .m|n12 / 78ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов12 / 78Количество неприводимых нормированных многочленовЛемма (о числе 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 / 78Количество неприводимых нормированных многочленов...Доказательство (продолжение)Поэтому все нормированные многочлены перечисляютсяформальным бесконечным произведением!∞Y XXkfi,n =fis11,n1 · . . . · fisrr,nri,n(∗)k=0(раскрыты скобки и бесконечное произведение записано в видеформального ряда).Сделаем замену переменных fi,n = tn , которая делает всемногочлены одной степени неразличимыми.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.

IIСуществование и единственность поля Галуа из pn элементов14 / 78Количество неприводимых нормированных многочленов...Доказательство (продолжение)!∞Y XXkfi,n=fis11,n1 · . . . · fisrr,nri,nk=0Приведение подобных приведёт к тому, что:в правой части (∗) будет ряд от переменной t.Коэффициент при tn в этом ряде равен числунормированных многочленов степени n, т.е.

pn :∞Xn=0pn tn .(∗)ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов15 / 78Количество неприводимых нормированных многочленов...Доказательство (продолжение)!∞∞Y XXkfi,n =pn tni,n(∗)n=0k=0в левой части все неприводимые многочлены степени nдадут одинаковый множитель (сумму бесконечнойгеометрической прогрессии со знаменателем tn ) и(∗) превращается в∞Y Xnk=0!dnnkt=∞Xn=0pn tn .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.

IIСуществование и единственность поля Галуа из pn элементов16 / 78Количество неприводимых нормированных многочленов...Доказательство (продолжение)По формуле суммы бесконечной геометрической прогрессии:1Yn(1 −tn )dn=1.1 − ptПрологарифмируем («−» в обеих частях равенствасокращаются, n 7→ m):Xdm ln(1 − tm ) = ln(1 − pt) .mПродифференцируем по t («−» в обеих частях равенствасокращаются):Xmtm−1pdm=.m1−t1−ptmПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов17 / 78Количество неприводимых нормированных многочленов...Доказательство (продолжение) (Xndnntn−1p=)1 − tn1 − ptСнова воспользуемся формулой суммой геометрическойпрогрессии:XXdm mtm−1 tmk =pn+1 tn .nm,kУмножаем на t обе части равенства:XXpn tn .mdm tm(k+1) =nm,kРавенство коэффициентовстепенях t и естьP при одинаковыхутверждение леммы (m · dm = pn ).m|nПРИКЛАДНАЯ АЛГЕБРА.

Часть I: Конечные поля или поля Галуа. IIСуществование и единственность поля Галуа из pn элементов18 / 78Важные замечания1. Существование неприводимых многочленовИз данной леммы следует неравенство ndn 6 pn . Простаяоценкаn−1XXpn − 1ndn = pn −kdk > pn −pk = pn −> 0.p−1k|n, k<nk=0доказывает, что dn > 0, а это означает, что существует хотя быодин неприводимый многочлен степени n.ПРИКЛАДНАЯ АЛГЕБРА.