AA3-1(GF-I) (1127138), страница 5
Текст из файла (страница 5)
Найти натуральное d и целые x и y такие, чтоd = НОД (252, 105) = 252x + 105y.Решение. Имеем xi = xi−2 − qi xi−1 , yi = yi−2 − qi yi−1 .Сведём все вычисления в таблицу:шаг i−2−1012ri−2ri−1qi252105421054221222ri25210542210xi101−2yi01−25Ответ: d = 21, x = −2, y = 5 ,т.е. найдено разложение 21 = (−2) · 252 + 5 · 105.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных полях35 / 71ЗадачаВ полеZ/(101)решить уравнение4x = 1.(∗).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных полях35 / 71ЗадачаВ полеZ/(101)решить уравнение4x = 1.Решение1 4x = 1 + k · 101 = 102, 203, 304, .
. . ;Это решение перебором.(∗).x = 304/4 = 76.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных полях35 / 71ЗадачаВ полеZ/(101)решить уравнение4x = 1.Решение1 4x = 1 + k · 101 = 102, 203, 304, . .
. ;Это решение перебором.2(∗).x = 304/4 = 76.Поскольку 101y ≡101 0, вместо (∗) можно расширеннымалгоритмом Евклида решать уравнение4x + 101y = 1 .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных полях35 / 71ЗадачаВ полеZ/(101)решить уравнение4x = 1.Решение1 4x = 1 + k · 101 = 102, 203, 304, . . . ;Это решение перебором.2(∗).x = 304/4 = 76.Поскольку 101y ≡101 0, вместо (∗) можно расширеннымалгоритмом Евклида решать уравнение4x + 101y = 1 .В результате работы алгоритма: 4 · 76 + 101 · (−3) = 1.Аналогично решаются уравненияax = c,ax + by = c(перед решением a, b и c надо поделить на их общий НОД).ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхНахождение обратных элементов в расширениях полейАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно,и в любом поле Галуа.36 / 71FpПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхНахождение обратных элементов в расширениях полей36 / 71FpАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно,и в любом поле Галуа.Поэтому: обратный элемент y(x) для некоторого многочленаb(x) в поле F = Fp [x]/(a(x)) определяется соотношениемb(x) · y(x) = 1⇔a(x) · χ(x) + b(x) · y(x) = 1 ,которое может быть решено расширенным алгоритмомЕвклида для пары многочленов (a(x), b(x)) в поле F .Решение данных уравнений существует всегда: т.к.
a(x) —неприводимый многочлен и deg b(x) < deg a(x), тоНОД (a(x), b(x)) = 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхПример: найти (x2 + x + 3)−1 в полеF7 [x]/37 / 71x4 + x3 + x2 + 3ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхПример: найти (x2 + x + 3)−1 в полеF7 [x]/37 / 71x4 + x3 + x2 + 3Применяя расширенный алгоритм Евклида, решим уравнение(x4 + x3 + x2 + 3)χ(x) + (x2 + x + 3)y(x) = 1(∗)ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхПример: найти (x2 + x + 3)−1 в полеF7 [x]/37 / 71x4 + x3 + x2 + 3Применяя расширенный алгоритм Евклида, решим уравнение(x4 + x3 + x2 + 3)χ(x) + (x2 + x + 3)y(x) = 1Шаг 0:Шаг 1:Шаг 2:(∗)r−2 (x) = x4 + x3 + x2 + 3,r−1 (x) = x2 + x + 3,y−2 (x) = 0,y−1 (x) = 1— задание начальных значений.r−2 (x) = r−1 (x)q0 (x) + r0 (x),q0 (x) = x2 + 5,r0 (x) = 2x + 2,y0 (x) = y−2 (x) − y−1 (x)q0 (x) = −q0 (x) = −x2 − 5.r−1 (x) = r0 (x)q1 (x) + r1 (x),q1 (x) = 4x,r1 (x) = 3, deg r1 (x) = 0y1 (x) = y−1 (x) − y0 (x)q1 (x) = 1 + 4x(x2 + 5) == 4x3 + 6x + 1.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IВычисление элементов в конечных поляхПример...F47 :38 / 71(x4 + x3 + x2 + 3)χ(x) + b(x)(x2 + x + 3) = 1 (∗)Алгоритм заканчивает свою работу на шаге 2, т.к. r1 (x) = 3 иdeg r1 (x) = deg 1 = 0 ( 1 — многочлен в правой части (∗) ).ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхПример...F47 :38 / 71(x4 + x3 + x2 + 3)χ(x) + b(x)(x2 + x + 3) = 1 (∗)Алгоритм заканчивает свою работу на шаге 2, т.к.
r1 (x) = 3 иdeg r1 (x) = deg 1 = 0 ( 1 — многочлен в правой части (∗) ).Замечание: при итерациях алгоритма нет необходимостивычислять χi (x) — коэффициент при x4 + x3 + x2 + 3, — т.к.нас интересует только yi (x) — коэффициент при x2 + x + 3.Остаток r1 (x) = 3, отличается от 1 на множитель-константу.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IВычисление элементов в конечных поляхПример...F47 :(x4 + x3 + x2 + 3)χ(x) + b(x)(x2 + x + 3) = 1 (∗)Алгоритм заканчивает свою работу на шаге 2, т.к.
r1 (x) = 3 иdeg r1 (x) = deg 1 = 0 ( 1 — многочлен в правой части (∗) ).Замечание: при итерациях алгоритма нет необходимостивычислять χi (x) — коэффициент при x4 + x3 + x2 + 3, — т.к.нас интересует только yi (x) — коэффициент при x2 + x + 3.Остаток r1 (x) = 3, отличается от 1 на множитель-константу.Чтобы получить решение уравнения (∗) вычисляем элемент3−1 ≡7 5 и домножаем на него y1 :5y1 (x) = 5(4x3 + 6x + 1) ≡7 6x3 + 2x + 5.Ответ: в поле38 / 71F7 [x]/x4 + x3 + x2 + 3 —(x2 + x + 3)−1 = 6x3 + 2x + 5.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа.
IЛинейная алгебра над конечным полемРазделы1Поля вычетов по модулю простого числа2Вычисление элементов в конечных полях3Линейная алгебра над конечным полем4Корни многочленов над конечным полем5Существование и единственность поля Галуа из pnэлементов6Циклические подпространства7Задачи с решениями8Что надо знать39 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемВекторное пространство: определениеОпределениеАбстрактным векторным пространством над полем k = { 1, α, β, . . . }называется алгебраическая система V = h V, k; +, · i, гдеV = { 0, v, . . . } — произвольное множество,++ — бинарная операция сложения над V : V × V → V ,· — бинарная операция умножения элемента («числа») из k на·элемент («вектор») из V : k × V → V ,40 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемВекторное пространство: определениеОпределениеАбстрактным векторным пространством над полем k = { 1, α, β, . . . }называется алгебраическая система V = h V, k; +, · i, гдеV = { 0, v, . . . } — произвольное множество,++ — бинарная операция сложения над V : V × V → V ,· — бинарная операция умножения элемента («числа») из k на·элемент («вектор») из V : k × V → V ,причём операции + и · удовлетворяют следующим аксиомам:L1: V — коммутативная группа по сложению, 0 — её нейтральныйэлемент.L2: α · (v1 + v2 ) = α · v1 + α · v2 , (α1 + α2 ) · v = α1 · v + α2 · v,(дистрибутивность · относительно +),L3: α · (β · v) = (αβ) · v (композиция умножений на два элементаполя совпадает с умножением их произведение,«ассоциативность» операций умножения поля и ·),L4: 1 · v = v (унитальность).40 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемКоординатное пространствоПримерПусть V = kn — множество конечных последовательностей длины nэлементов поля k.’Сложение’ и ’умножение на число (из k)’ элементов из Vопределяются покомпонентно.Получившаяся структура — векторное пространство.Его называют n-мерным координатным пространством над полем k.Дистрибутивность относительно вычитания: (α − β) · v = α · v − β · v:(α − β) · v + β · v = (α − β + β) · v = α · vОтсюда получаем, что0 · v = 0, так как 0 · v = (1 − 1) · v = v − v = 0и −v = (−1) · v, так какv + (−1) · v = 1 · v + (−1) · v = (1 − 1) · v = 0 · v = 0.41 / 71ПРИКЛАДНАЯ АЛГЕБРА.
Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полем42 / 71Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство над Fp .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полем42 / 71Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство над Fp .Доказательствосложение — наследуется операция сложения в поле k;p−1умножение — посколькуz }| { Fp ∼= F = 0, 1, 1 + 1, .
. . , 1 + . . . + 1 ⊆ k,то при умножении «числа» из поля Fp можнозаменять на соответствующие элементы из поля F ;аксиомы векторного пространства — выполняются в силусвойств арифметических операций в поле k.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полем42 / 71Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство над Fp .Доказательствосложение — наследуется операция сложения в поле k;p−1умножение — посколькуz }| { Fp ∼= F = 0, 1, 1 + 1, .
. . , 1 + . . . + 1 ⊆ k,то при умножении «числа» из поля Fp можнозаменять на соответствующие элементы из поля F ;аксиомы векторного пространства — выполняются в силусвойств арифметических операций в поле k.СледствиеПоле Галуа как векторное пространство состоит из pn элементов.ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полем43 / 71Поля Галуа как кольца вычетов или векторные пространстваПолеFnpесть конечная АС с элементами-многочленамиMn (x) =a0 + a1 x + .
. . + an−1 xn−1⊂Fp [x],которую можно рассматривать какфакторкольцо вычетов по модулю некоторогонеприводимого многочлена f (x) степени n над полемFnp ∼= Fp [x]/(f (x)) ; +p , ·pили какn-мерное координатное пространство над полемFnp ∼= Mn (x), Fp ; +p , ·p .Fp :Fp :ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемБазис в44 / 71FnpТеоремаЭлементы {1}, {x}, . . . , {xn−1 } образуют базисFnp .ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. IЛинейная алгебра над конечным полемБазис в44 / 71FnpТеоремаЭлементы {1}, {x}, . . . , {xn−1 } образуют базисFnp .Доказательство1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
