Лекции по прикладной алгебре. v1.1 (1127111), страница 4
Текст из файла (страница 4)
. . ;Это решение перебором.(∗)x = 304/4 = 76.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 160ЗадачаВ поле Z/(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 102, 203, 304, . . . ;Это решение перебором.2(∗)x = 304/4 = 76.Поскольку 101y ≡101 0, вместо (∗) можно расширеннымалгоритмом Евклида решать уравнение4x + 101y = 1 .Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 160ЗадачаВ поле Z/(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 102, 203, 304, .
. . ;Это решение перебором.2(∗)x = 304/4 = 76.Поскольку 101y ≡101 0, вместо (∗) можно расширеннымалгоритмом Евклида решать уравнение4x + 101y = 1 .В результате работы алгоритма: 4 · 76 + 101 · (−3) = 1.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 160ЗадачаВ поле Z/(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 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 надо поделить наНОД).Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхНахождение обратных элементов в расширениях полей36 / 160FnАлгоритм Евклида (а также его расширенная версия) остаётсясправедливым в любом евклидовом кольце.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях36 / 160Нахождение обратных элементов в расширениях полейFnАлгоритм Евклида (а также его расширенная версия) остаётсясправедливым в любом евклидовом кольце.Пусть f (x) – неприводимый многочлен степени n над Fp .
Тогдаобратный элемент h для некоторого многочлена g в полеFnp = Fp [x]/(f (x)) определяется условиемg(x) · h(x) = 1илиf (x) · a(x) + g(x) · h(x) = 1 .Оно может быть решено путем применения расширенногоалгоритма Евклида для пары многочленов (f, g).Заметим, что решение данного уравнения существует всегда:f – неприводимый полином, deg g < deg f ⇒ НОД(f, g) = 1.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример: найти (x2 + x + 3)−1 в поле37 / 160F7 [x]/(x4 + x3 + x2 + 3)Применяя расширенный алгоритм Евклида, решим уравнение(x4 + x3 + x2 + 3) · a(x) + (x2 + x + 3) · b(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.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...Алгоритм заканчивает свою работу на шаге 2, т.к.deg r1 (x) = deg 1 (1 — многочлен в правой части (∗) ).38 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...Алгоритм заканчивает свою работу на шаге 2, т.к.deg r1 (x) = deg 1 (1 — многочлен в правой части (∗) ).Замечание: итерациях алгоритма нет необходимости вычислятьxi (x) (коэффициент при x4 + x3 + x2 + 3), т.к.
нас интересуеттолько yi (x) — коэффициент при x2 + x + 3.38 / 160Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...Алгоритм заканчивает свою работу на шаге 2, т.к.deg r1 (x) = deg 1 (1 — многочлен в правой части (∗) ).Замечание: итерациях алгоритма нет необходимости вычислятьxi (x) (коэффициент при x4 + x3 + x2 + 3), т.к. нас интересуеттолько yi (x) — коэффициент при x2 + x + 3.Остаток r1 (x) = 3, т.е.
отличается от 1 намножитель-константу.Чтобы получить решение уравнения (∗) вычисляем элемент3−1 ≡7 5 и домножаем на него y1 :5 · y1 (x) = 5 · (4x3 + 6x + 1) = 6x3 + 2x + 5.Ответ: в полеF7 [x]/(x4 + x3 + x2 + 3)(x2 + x + 3)−1 = 6x3 + 2x + 5.38 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиОсновная задача теории кодированияЦиклические коды39 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел IIКоды БЧХЧто надо знать40 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемВекторное пространство: определениеОпределениеАбстрактным векторным пространством над полем k = {α, .
. .}называется двухосновная алгебраическая система V = h V, k; +, · i, гдеV = {0, v, . . .} — произвольное множество,++ — бинарная операция сложения над V : V × V → V ,· — бинарная операция умножения элемента («числа») из k на·элемент («вектор») из V : k × V → V ,41 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемВекторное пространство: определениеОпределениеАбстрактным векторным пространством над полем k = {α, . . .}называется двухосновная алгебраическая система 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 (унитальность).41 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемКоординатное пространствоПримерПусть V = kn — множество последовательностей длины n,составленных из элементов поля k.Сложение и умножение на число определяются покомпонентно.Получившаяся структура — векторное пространство.Его называют n-мерным координатным пространством над полем k.42 / 160Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем43 / 160Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство надFp .Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем43 / 160Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство надДоказательствосложение — наследуется операция сложения в поле k;умножение — подмножествоF = {0, 1, 1 + 1, .
. . , 1| + .{z. . + 1}} ⊆ kp−1есть подполе, изоморфное Fp , что позволяетзаменять при умножении «числа» из Fp насоответствующие элементы из F ;аксиомы векторного пространства — выполняются в силусвойств арифметических операций в поле k.Fp .Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем43 / 160Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство надДоказательствосложение — наследуется операция сложения в поле k;умножение — подмножествоF = {0, 1, 1 + 1, . . . , 1| + .{z. . + 1}} ⊆ kp−1есть подполе, изоморфное Fp , что позволяетзаменять при умножении «числа» из Fp насоответствующие элементы из F ;аксиомы векторного пространства — выполняются в силусвойств арифметических операций в поле k.СледствиеКонечное поле (как векторное пространство) состоит из pnэлементов, p — простое, n — натуральное.Fp .Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем44 / 160Поля Галуа как кольца вычетов или векторные пространстваПолеFnp есть конечная АС с элементами-многочленамиM = { a0 + a1 x + .
. . + an−1 xn−1 } ⊂ Fp [x],которую можно рассматривать какфакторкольцо вычетов по модулю некоторогонеприводимого многочлена f (x) степени n над полемFnp= h Fp [x]/(f (x)); +p , ·p iили какn-мерное координатное пространство над полемFnp= h M, Fp ; +p , ·p i .Fp :Fp :Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемБазис в45 / 160FnpТеоремаЭлементы 1, x, . . .
, xn−1 образуют базисFnp .Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемБазис в45 / 160FnpТеоремаЭлементы 1, x, . . . , xn−1 образуют базисFnp .ДоказательствоЛюбой элемент Fnp представим в виде линейнойкомбинации указанных векторов:a0 + a1 x + . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
