PA_full (1127144), страница 4
Текст из файла (страница 4)
числа в паре уменьшаются,но остаются неотрицательными.В результате: за конечное число шагов образуется пара (rn , 0).Ясно, что НОД(a, b) = rn .Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях34 / 432Алгоритм Евклида: общая схема (a > b)НОД(a, b) = ?Шаг ( 2): r2= a � полагаем для удобства;Шаг ( 1): r1= b � полагаем для удобства;Шаг 0: r2= r1 q0+ r0 � делим r2на r1,остаток r0 ;Шаг 1: r 1 = r0 q1 + r1 � делим r 1 на r0 , остаток r1 ;... всегда делим с остатком бо́льшее число наменьшее, оставляем меньшее (оно становитсябо́льшим) и остаток;Шаг n: rn 2 = rn 1 qn + rn � делим rnостаток rn ;Шаг n + 1: rn1>r1Всегда r22на rn1,= rn qn+1 + 0 � деление нацело ) останов.> r0 > r1 > . . . > rn > 1. НОД(a, b) = rn .Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхАлгоритм Евклида: примерНОД(252, 105) =?35 / 432Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 432Алгоритм Евклида: примерНОД(252, 105) =?Шаг ( 2): r2= 252;Шаг ( 1): r1= 105) (252, 105);Шаг 0: 252 = 105 · 2 + 42) (105, 42);Шаг 1: 105 = 42 · 2 + 21) (42, 21);Шаг 2: 42 = 21 · 2 + 0) (21, 0).НОД(252, 105) = 21.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях35 / 432Алгоритм Евклида: примерНОД(252, 105) =?Шаг ( 2): r2= 252;Шаг ( 1): r1= 105) (252, 105);Шаг 0: 252 = 105 · 2 + 42) (105, 42);Шаг 1: 105 = 42 · 2 + 21) (42, 21);Шаг 2: 42 = 21 · 2 + 0) (21, 0).НОД(252, 105) = 21.НОД(a, b, c) = НОД(a, (НОД(b, c))Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях36 / 432Теорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если d = НОД(a, b), то найдутся x, y 2такие, что d = ax + by.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях36 / 432Теорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если d = НОД(a, b), то найдутся x, y 2такие, что d = ax + by.ДоказательствоРассматриваем алгоритм Евклида с конца к началу:d = rn = rn 2 rn 1 qn , затем, подставляя сюда значениеrn 1 = rn 3 rn 2 qn 1 , получаемd = qn rn 3 + (1 + qn qn 1 )rn 2 = ↵rn 3 + rn 2для некоторых ↵, 2 и т.д.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях36 / 432Теорема Безу и расширенный алгоритм ЕвклидаТеорема (Безу)Если d = НОД(a, b), то найдутся x, y 2такие, что d = ax + by.ДоказательствоРассматриваем алгоритм Евклида с конца к началу:d = rn = rn 2 rn 1 qn , затем, подставляя сюда значениеrn 1 = rn 3 rn 2 qn 1 , получаемd = qn rn 3 + (1 + qn qn 1 )rn 2 = ↵rn 3 + rn 2для некоторых ↵, 2 и т.д.Для нахождения по паре натуральных чисел (a, b) натурального dи пары целых (x, y) таких, чтоd = НОД(a, b) = ax + ay,применяют расширенный алгоритм Евклида.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях37 / 432Расширенный алгоритм ЕвклидаРасширенный алгоритм Евклида повторяет схему (простого)алгоритма Евклида, в котором на каждом шаге:дополнительно вычисляются xi и yi по формуламxi = xiqi x i21,xy i = yi2= y12qi yi1,i = 0, 1, ...;= 1.справедливо соотношениеri = ri2q i ri= a(xi21= (axiqi xi1)2 +byi 2 )+ b(yi2qi (axiqi yi1)1 +byi 1 )== axi + byi .Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях38 / 432Расширенный алгоритм Евклида: примерЗадача.
Найти натуральное d и целые x и y такие, чтоd = НОД(a, b) = 252x + 105y.Решение. Имеем xi = xi 2 qi xi 1 , yi = yiСведём все вычисления в таблицу:шаг i-2-1012Ответ: d = 21, x =ri225210542ri1qi10542212222, y = 5.ri25210542210xi101-22qi yiyi01-251.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле /(101) решить уравнение4x = 1.(⇤)Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле /(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 102, 203, 304, .
. . ;Это решение перебором.(⇤)x = 304/4 = 76.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле /(101) решить уравнение4x = 1.Решение1 4x = k · 101 + 1 = 102, 203, 304, . . . ;Это решение перебором.2(⇤)x = 304/4 = 76.Поскольку 101y ⌘101 0, вместо (⇤) можно расширеннымалгоритмом Евклида решать уравнение4x + 101y = 1 .Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях39 / 432ЗадачаВ поле /(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ЗадачаВ поле /(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 / 432pАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно, и влюбом поле Галуа.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях40 / 432Нахождение обратных элементов в расширениях полейpАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно, и влюбом поле Галуа.Поэтому:обратный элемент y(x) для некоторого многочлена b(x) в полеF = p [x]/(a(x)) определяется соотношениемb(x) · y(x) = 1,a(x) · (x) + b(x) · y(x) = 1.Прикладная алгебраПоля ГалуаВычисление элементов в конечных полях40 / 432Нахождение обратных элементов в расширениях полейpАлгоритм Евклида и его расширенная версия остаётсясправедливым в любом евклидовом кольце, следовательно, и влюбом поле Галуа.Поэтому:обратный элемент y(x) для некоторого многочлена b(x) в полеF = p [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)41 / 4321в поле7 [x]/(x4+ x3 + x2 + 3)Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример: найти (x2 + x + 3)41 / 4321в поле7 [x]/(x4+ x3 + x2 + 3)Применяя расширенный алгоритм Евклида, решим уравнениеa(x)(x4 + x3 + x2 + 3) + b(x)(x2 + x + 3) = 1(⇤)Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример: найти (x2 + x + 3)41 / 4321в поле7 [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.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...4742 / 432: a(x)(x4 + x3 + x2 + 3) + b(x)(x2 + x + 3) = 1 (⇤)Алгоритм заканчивает свою работу на шаге 2, т.к.
r1 (x) = 3 иdeg r1 (x) = deg 1 = 0 (1 � многочлен в правой части (⇤) ).Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...4742 / 432: 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.Прикладная алгебраПоля ГалуаВычисление элементов в конечных поляхПример...4742 / 432: 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.Ответ: в поле47 [x]/(x(x2 + x+ x3 + x2 + 3)+ 3)1= 6x3 + 2x + 5.Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды43 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств44 / 432Прикладная алгебраПоля ГалуаЛинейная алгебра над конечным полемРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
