Лекции по прикладной алгебре. v2.0 (1127112), страница 4
Текст из файла (страница 4)
Найти натуральное d и целые x и y такие, чтоd = НОД(a, b) = 252x + 105y.Решение. Имеем xi = xi−2 − qi xi−1 , yi = yi−2 − qi yi−1 .Сведём все вычисления в таблицу:шаг i-2-1012ri−2ri−1qi252105421054221222Ответ: d = 21, x = −2, y = 5.ri25210542210xi101-2yi01-25Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле Z/(101) решить уравнение4x = 1.(∗)Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле Z/(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 102, 203, 304, . . . ;Это решение перебором.(∗)x = 304/4 = 76.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле Z/(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 102, 203, 304, .
. . ;Это решение перебором.2(∗)x = 304/4 = 76.Поскольку 101y ≡101 0, вместо (∗) можно расширеннымалгоритмом Евклида решать уравнение4x + 101y = 1 .Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле 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.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле 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 надо поделить на их общий НОД).Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхНахождение обратных элементов в расширениях полей40 / 432FpАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно, и влюбом поле Галуа.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях40 / 432Нахождение обратных элементов в расширениях полейFpАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно, и влюбом поле Галуа.Поэтому:обратный элемент y(x) для некоторого многочлена b(x) в полеF = Fp [x]/(a(x)) определяется соотношениемb(x) · y(x) = 1⇔a(x) · χ(x) + b(x) · y(x) = 1.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях40 / 432Нахождение обратных элементов в расширениях полейFpАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно, и влюбом поле Галуа.Поэтому:обратный элемент y(x) для некоторого многочлена b(x) в полеF = Fp [x]/(a(x)) определяется соотношениемb(x) · y(x) = 1⇔a(x) · χ(x) + b(x) · y(x) = 1.Оно может быть решено путем применения расширенногоалгоритма Евклида для пары многочленов (a, b) в поле F .Решение данных уравнений существует всегда: поскольку a —неприводимый многочлен и deg b < deg a ⇒ НОД(a, b) = 1.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример: найти (x2 + x + 3)−1 в поле41 / 432F7 [x]/(x4 + x3 + x2 + 3)Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример: найти (x2 + x + 3)−1 в поле41 / 432F7 [x]/(x4 + x3 + x2 + 3)Применяя расширенный алгоритм Евклида, решим уравнениеa(x)(x4 + x3 + x2 + 3) + b(x)(x2 + x + 3) = 1(∗)Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример: найти (x2 + x + 3)−1 в поле41 / 432F7 [x]/(x4 + x3 + x2 + 3)Применяя расширенный алгоритм Евклида, решим уравнениеa(x)(x4 + x3 + x2 + 3) + b(x)(x2 + x + 3) = 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.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...F47 :42 / 432a(x)(x4 + x3 + x2 + 3) + b(x)(x2 + x + 3) = 1 (∗)Алгоритм заканчивает свою работу на шаге 2, т.к.
r1 (x) = 3 иdeg r1 (x) = deg 1 = 0 (1 — многочлен в правой части (∗) ).Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...F47 :42 / 432a(x)(x4 + x3 + x2 + 3) + 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.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...F47 :a(x)(x4 + x3 + x2 + 3) + 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.Ответ: в поле42 / 432F7 [x]/(x4 + x3 + x2 + 3)(x2 + x + 3)−1 = 6x3 + 2x + 5.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды43 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств44 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать45 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемВекторное пространство: определениеОпределениеАбстрактным векторным пространством над полем k = {α, . . .}называется двухосновная алгебраическая система V = h V, k; +, · i, гдеV = {0, v, .
. .} — произвольное множество,++ — бинарная операция сложения над V : V × V → V ,· — бинарная операция умножения элемента («числа») из k на·элемент («вектор») из V : k × V → V ,46 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемВекторное пространство: определениеОпределениеАбстрактным векторным пространством над полем 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 (унитальность).46 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемКоординатное пространствоПримерПусть V = kn — множество последовательностей длины n,составленных из элементов поля k.Сложение и умножение на число определяются покомпонентно.Получившаяся структура — векторное пространство.Его называют 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 .47 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем48 / 432Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство надFp .Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем48 / 432Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство надДоказательствосложение — наследуется операция сложения в поле k;умножение — посколькуp−1z }| {∼ F = { 0, 1, 1 + 1, .
. . , 1 + . . . + 1 } ⊆ k,Fp =Fp .то при умножении «числа» из поля Fp можнозаменять на соответствующие элементы из поля F ;аксиомы векторного пространства — выполняются в силусвойств арифметических операций в поле k.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полем48 / 432Применение линейной алгебры к изучению конечных полейЛеммаПоле k характеристики p > 0 есть векторное пространство надДоказательствосложение — наследуется операция сложения в поле k;умножение — посколькуp−1z }| {∼ F = { 0, 1, 1 + 1, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
