Экзаменационный теоретический минимум (ответы) (1127336), страница 2
Текст из файла (страница 2)
Пусть нужно найти обратный элемент y(x) к b(x).y(x) ∗ b(x) = 1 ⟺ a(x) ∗ x(x) + b(x) ∗ y(x) = 1Алгоритм Евклида применим для евклидовых колец. Пример такого кольца - кольцо многочленов.Понятие поля. Построение конечных полей с помощью неприводимых многочленов(привести пример). Полиномиальное и степенное представление элементов поля.ПолеПоле — алгебра над множеством F , образующая коммутативную группу по сложению + над F с нейтральным элементом 0 икоммутативную группу по умножению над ненулевыми элементами F ∖ {0}, при выполняющемся свойстве дистрибутивностиумножения относительно сложения.Характеристика поляkПусть F - произвольное поле.
1 - единица F . В конечном поле всегда найдется первое k, что ∑i=1 1характеристикой поля F .= 0. Число k будем называтьСвойства:Характеристика поля всегда 0 или простое число.Поле характеристики 0 содержит подполе, изоморфное полю рациональных чисел Q.Поле простой характеристики p содержит подполе, изоморфное полю вычетов Zp .Количество элементов в конечном поле всегда равно pn — степени простого числа.При этом для любого числа вида pn существует единственное (с точностью до изоморфизма) поле из pn элементов,обычно обозначаемое Fpn .В поле нет делителей нуля.Любая конечная подгруппа мультипликативной группы поля является циклической. В частности, мультипликативная группаненулевых элементов конечного поля Fq изоморфна Zq−1 .Примеры полей:Q — рациональные числа,R — вещественные числа,C — комплексные числа,Zp — поле вычетов по модулю p, где p — простое число.Fq — конечное поле из q = pk элементов, где p — простое число, k — натуральное.
Все конечные поля имеют такой вид.F(x) — поле рациональных функций вида f(x)/g(x), где f и g — многочлены над некоторым полем F (при этом g ≠ 0, а fи g не имеют общих делителей, кроме констант).Неприводимый многочлен — многочлен, неразложимый на нетривиальные (неконстантные) многочлены. В поле R существуютнеприводимые многочлены 1-й и 2-й степени(с отрицательным дискриминантом) В поле C существуют неприводимые многочлены1-йПостроение поля ГалуаПоле GF(pn ) при n>1 строится как факторкольцо K = Zp [x]/⟨f(x)⟩, где f(x) — неприводимый многочлен степени n над полемZp .
Таким образом, для построения поля из pn элементов достаточно отыскать многочлен степени n , неприводимый над полем Zp .Элементами поля K являются все многочлены степени меньшей n с коэффициентами из Zp . Арифметические операции (сложение иумножение) проводятся по модулю многочлена f(x), то есть, результат соответствующей операции — это остаток от деления на f(x)с приведением коэффициентов по модулю p.Пример построения поля GF(9)Для построения поля GF(9)являются:= GF(32 ) необходимо найти многочлен степени 2, неприводимый над Z3 . Такими многочленамиx2 + 1x2 + x + 2x2 + 2x + 22x2 + 22x2 + x + 12x2 + 2x + 1Возьмём, например, x2 + 1, тогда искомое поле есть GF(9)получится новое поле, изоморфное старому.= Z3 [x]/⟨x2 + 1⟩.
Если вместо x2 + 1 взять другой многочлен, тоТаблица сложения в GF(9)GF(9) = Z3 [x]/⟨x2 + 1⟩+012x00121120201xx+1x+22x2x + 12x + 2x+1x+2x2x + 12x + 22xx+2xx+12x + 22x2x + 12xx+1x+22x2x + 12x + 2Таблица умножения в GF(9)GF(9) = Z3 [x]/⟨x2 + 1⟩xx+1x+22x2x + 12x + 2012x+1x+1x+2x2x + 12x + 22xx + 2 2xx+22xx 2x + 1x + 1 2x + 202x + 212x22x + 112x20 x+101 x+22x + 1 2x + 22x + 1 2x + 22x + 22x2x 2x + 1122001x+1 x+2xx+2x x+1×012000010122021xx+1x+22x2x + 12x + 20xx+1x+22x2x + 12x + 22x2x + 22x + 1xx+2x+100000x+1 x+2x000x x+12x 2x + 22 x+2x+22x12x + 21 2x + 12x+1x2x + 1x+22x + 12x + 21xx+12x22x2x + 1 2x + 20002x 2x + 1x x+21 x+122x + 1x+12x2 2x + 2x2x + 21x+22x + 2x+12x + 1x2x+212xСтепенное представление элементов поляЗаметим, что(x + 1)1(x + 1)2(x + 1)3(x + 1)4(x + 1)5(x + 1)6(x + 1)7(x + 1)8=x+1= 2x= 2x + 1=2= 2x + 2=x=x+2=1Следовательно, x + 1 является примитивным элементом построенного поля.
Если a - примитивным элемент поля GF(q), то любойдругой элемент поля может быть получен как степень ak , где k - целое число, взаимно простое с q − 1.Алгоритм нахождения всех корней многочленанад полемРазложим многочлен f(x) на неприводимые множители над Fpf(x) = g1 (x) ∗ g2 (x) ∗ … ∗ gk (x)∈ {1, … k} рассмотреть расширение Fp [x]/⟨gi (x)⟩, в котором он будет иметь корниppdeg(gi −1)α, α , … , αЗаписать эти корни как многочлены из Fp [x]/⟨g i (x)⟩mОбъединить все корни в общем расширении Fp , где m = LCM(deg(g1 ), … , deg(g k ))Для каждого многочлена gi (x), iИсточник: 148 слайд (311 страница)Минимальные многочлены для элементов конечного поля.
Алгоритм нахожденияминимального многочлена.Рассмотрим поле Fp , в нем какой-нибудь элемент β и будет интересоваться многочленами, для которых β является корнем.nМногочлен m(x) называется минимальным многочленом, если m(x) - нормированный многочлен минимальной степени, длякоторого β является корнем.Построение:= Fp [x]/⟨a(x)⟩, где a(x) = a0 + a1 ∗ x + a2 ∗ x2 + ⋯ + an ∗ xn - неприводимый многочлен.
Тогдадля элемента x ∈ F многочлен a−1n ∗ a(x) - минимальный.Пусть задано поле FТеорема Хэмминга. Пример построения кода Хэмминга.ОпределениеПусть n - длина кода, r - максимальное допустимое число ошибок.Теорема ХэммингаПри 2 ∗ r< n максимальное число кодовых слов t находится в пределах:2nn(n0 ) + (n1 ) + … + (2∗r)≤t≤2n(n0 ) + (n1 ) + … + (nr)ПримерПостроим код Хэмминга длины 7.
Выпишем таблицу: n = 2q − 1 → q = 3, r = 1 Матрица состоит из единичной матрицы,размерности 2q − q − 1 и матрицы из бинарных наборов(различных) длины q, содержащих не менее 2-x единиц.1 0 0 0 1 0 10 1 0 0 1 1 00 0 1 0 0 1 10 0 0 1 1 1 1Складывая строки произвольным образом (mod 2), получим 16 возможных сообщений. При их получении можно будет исправить однуошибку.Коды БЧХ: определение, примеры кодов с исправлением одной, двух и трех ошибок.БЧХ коды - класс циклических кодов, исправляющих кратные (2 и более ошибок). БЧХ код задается порождающим полиномом.
Дляего построения необходимо задать длину кода и требуемое минимальное расстояние d ≤ n.Построение БЧХ кодов:Строим поле F2= F2 [x]/⟨f⟩, где f - неприводимый многочлен степени n = 2m − 1.n∗n∗Выберем в циклической группе F2 примитивный элемент α ∈ F2 и рассмотрим его степени: α, α2 , ⋯ , α2∗r , где r - числоnошибок, которые нужно исправить.В разложении многочлена xn − 1 выберем такие неприводимые многочлены, чтобы каждая из указанных степеней была корнемодного из них (это не всегда возможно). Тогда:ϕ есть результат перемножения этих многочленовкоды - коэффициенты многочленов из идеала (ϕ)эти коды исправляют r ошибокПример кода, исправляющего 1 ошибку3= F2 [x]/(x3 + x + 1). r=3, m=2.
Многочлен x3 + x + 1 - примитивный над F2 . Порождающий полиномx + x + 1, т.к пусть α - его произвольный корень, тогда остальные корни α2 , α4 и они входят в один смежный класс.Рассмотрим поле F23Пример кода, исправляющего 2 ошибки4Рассмотрим поле F2= F2 [x]/(x15 − 1). α, α2 , α3 , α4x4 + x + 1 x4 + x3 + 1Пример кода, исправляющего 3 ошибкиr = 3, m = 4, f(x) = x15 − 1.
Следовательно, нужно найти многочлены, корнями которых будут первые 2 ∗ r = 6 степенейпорождающего элемента αесли многочлен имеет корень то у него есть корни1αα2 , α4 , α82α3α2 , α4 , α83α5α10Перемножим полученные многочлены, получим многочлен 10-й степени. (первые 2 - четвертой, последний - второй). Идеал по модулюэтого многочлена дает 5 степеней свободы, следовательно, построенный код будет 5-мерным пространством.Понятие действия группы на множестве, фиксатор и стабилизатор. Примеры.Гомоморфизм групп - Отображение групп f: (G, ∗) → (H, ×)такое, что f(a ∗ b) = f(a) × f(b)для произвольных a и b в G.Симметрической группой множества X называется группа всех перестановок X (то есть биекций X→ X) относительнооперации композиции.Инверсная группа — построение в теории групп, сменяющее аргументы бинарной групповой операции местами, используемое дляопределения правого действия.Действие слеваГоворят, что группа G действует слева на множестве M , если задан гомоморфизм Φ: G → S(M) из группы G всимметрическую группу S(M) множества M .
Для краткости (Φ(g))(m) часто записывают как gm , g ⋅ m или g. m . Элементыгруппы G называются в этом случае преобразованиями, а сама группа G — группой преобразований множества M .Другими словами, группа G действует на множестве M , если задано отображение Gтакое что1.2.× M → M . обозначаемое (g, m) = gm,(gh)m = g(hm) для всех g, h ∈ G , m ∈ M иem = m, где e — нейтральный элемент группы G . Можно сказать, что единица группы соотносит каждому элементу M егоже; такое преобразование называется тождественным.Действие справаopopАналогично, правое действие группы G на M задается гомоморфизмом ρ : G → S(M), где G — инверсия группы G . Приэтом часто используют сокращенное обозначение: ρ(g)(m) =: xg.
При этом аксиомы гомоморфизма записываются следующимобразом:1.2.m(gh) = (mg)h,me = m.КомментарииopЛюбое правое действие группы G — это левое действие группы G . Также, так как каждая группа изоморфна своейинверсной группе (изоморфизмом является, например, отображение g ↦ g −1 ), то из каждого правого действия можно спомощью такого изоморфизма получить левое действие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
