WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 1 / 78 Часть I Конечные поля или поля Галуа. II ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 2 / 78 Поля вычетов по ...»

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 1 / 78

Часть I

Конечные поля или поля Галуа.

II

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 2 / 78

Поля вычетов по модулю простого числа

Разделы

Поля вычетов по модулю простого числа

Вычисление элементов в конечных полях

Линейная алгебра над конечным полем

Корни многочленов над конечным полем

Существование и единственность поля Галуа из pn

элементов

Циклические подпространства

Задачи с решениями Что надо знать ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 3 / 78 Вычисление элементов в конечных полях Разделы Поля вычетов по модулю простого числа Вычисление элементов в конечных полях Линейная алгебра над конечным полем Корни многочленов над конечным полем Существование и единственность поля Галуа из pn элементов Циклические подпространства Задачи с решениями Что надо знать ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 4 / 78 Линейная алгебра над конечным полем Разделы Поля вычетов по модулю простого числа Вычисление элементов в конечных полях Линейная алгебра над конечным полем Корни многочленов над конечным полем Существование и единственность поля Галуа из pn элементов Циклические подпространства Задачи с решениями Что надо знать ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 5 / 78 Корни многочленов над конечным полем Разделы Поля вычетов по модулю простого числа Вычисление элементов в конечных полях Линейная алгебра над конечным полем Корни многочленов над конечным полем Существование и единственность поля Галуа из pn элементов Циклические подпространства Задачи с решениями Что надо знать ПРИКЛАДНАЯ АЛГЕБРА.


Часть I: Конечные поля или поля Галуа. II 6 / 78 Существование и единственность поля Галуа из pn элементов Разделы Поля вычетов по модулю простого числа Вычисление элементов в конечных полях Линейная алгебра над конечным полем Корни многочленов над конечным полем Существование и единственность поля Галуа из pn элементов Циклические подпространства Задачи с решениями Что надо знать ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 7 / 78 Существование и единственность поля Галуа из pn элементов Вычисления в мультипликативной группе расширения поля

–  –  –

Сделаем это, взяв многочлен f (x) = x4 + x + 1.

Будем задавать элементы F4 наборами коэффициентов многочлена-остатка при делении на f, записывая их в порядке возрастания степеней.

Порождающим является элемент = x, который записывается как (0, 1, 0, 0).

Вычислим степени, сведя результаты в таблицу.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 8 / 78 Существование и единственность поля Галуа из pn элементов

–  –  –

Существование неприводимого многочлена Докажем существование нормированного неприводимого многочлена в полях Галуа.

Для таких многочленов выполняется аналог основной теоремы арифметики: каждый нормированный многочлен однозначно разлагается на произведение степеней неприводимых многочленов.

Действительно:

разложение в евклидовом кольце однозначно (с точностью до умножения на обратимые элементы делители);

в случае кольца многочленов над полем обратимые элементы ненулевые константы (многочлены степени 0);

выбор старшего коэффициента 1 однозначно определяет сомножители.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 12 / 78 Существование и единственность поля Галуа из pn элементов Количество неприводимых нормированных многочленов

–  –  –

(раскрыты скобки и бесконечное произведение записано в виде формального ряда).

Сделаем замену переменных fi,n = tn, которая делает все многочлены одной степени неразличимыми.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 14 / 78 Существование и единственность поля Галуа из pn элементов доказывает, что dn 0, а это означает, что существует хотя бы один неприводимый многочлен степени n.

2. Среднее число неприводимых нормированных многочленов Из данной леммы вытекает, что при n имеем dn pn /n.

Т.е. неприводимые нормированные многочлены составляют приблизительно 1/n-ю часть всех многочленов степени n над полем Fp.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 19 / 78 Существование и единственность поля Галуа из pn элементов Изоморфизм полей Галуа с одинаковым числом элементов

–  –  –

В приложениях часто используется кольцо многочленов K(p, f ) = Fp [x]/(f ) по модулю главного идеала (f ) возможно приводимого многочлена f Fp [x].

–  –  –

Нормированный делитель порождающего элемента идеала Теорема Пусть неприводимый нормированный многочлен, который делит f. Тогда совокупность всех вычетов, кратных, образует идеал в

–  –  –

Подыдеал как векторное пространство Теорема Пусть неприводимый нормированный делитель многочлена f Fp [x] отличный от f, deg f = n, deg = k.

Тогда идеал () векторное пространство размерности n k.

Доказательство Без доказательства.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 26 / 78 Циклические подпространства Циклическое пространство: определение

–  –  –

Определение Подпространство координатного пространства F n называется циклическим, если вместе с набором (a0,..., an1 ) оно содержит циклический сдвиг (вправо) этого набора, т.е. набор (an1, a0,..., an2 ) (а следовательно и все циклические сдвиги на произвольное число позиций влево и вправо).

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 27 / 78 Циклические подпространства Кольцо классов вычетов по модулю многочлена xn 1

–  –  –

Вывод: корни уравнения xn 1 = 0 образуют группу корней степени n из единицы подгруппу в F. q Эта подгруппа также циклическая; её порождающие элементы называются примитивными корнями степени n.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 30 / 78 Циклические подпространства Количество и степени неприводимых делителей xn 1 Подгруппа в циклической группе существует i её порядок делит порядок циклической группы поле Fq содержит группу корней из единицы степени n i n | (q 1).

–  –  –

Поэтому x15 1 разлагается в произведение одного неприводимого многочлена степени 1, одного неприводимого многочлена степени 2, трех неприводимых многочленов степени 4.

Конкретно (разложение было раньше): x15 + 1 = = (x + 1)(x2 + x + 1)(x4 + x + 1)(x4 + x3 + 1)(x4 + x3 + x2 + x + 1).

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 32 / 78 Циклические подпространства

–  –  –

Пример Рассмотрим разложение многочлена x23 1 над F2.

Относительно умножения на 2 вычеты по модулю 23 разбиваются на три орбиты:

{ 0 }, { 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12 }, { 5, 10, 20, 17, 11, 22, 21, 19, 15, 7, 14 } (18 · 2 = 36 23 13) Поэтому x23 1 разлагается в произведение одного неприводимого многочлена степени 1 и двух неприводимых многочленов степени 11.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 33 / 78 Задачи с решениями

–  –  –

Что надо знать ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 34 / 78 Задачи с решениями Задача ПГ-1 (теорема Вильсона)

–  –  –

Построить поле из 4-х элементов.

Решение Это поле F2, оно может быть построено как фактор-кольцо F2 [x]/ (a(x)), где a(x) неприводимый многочлен из F2 [x] степени 2.

Но такой многочлен только один: x2 + x + 1.

Следовательно, F2 = { 0, 1, x, x + 1 }

–  –  –

Найти все нормированные многочлены второй степени от x, неприводимые над полем вычетов по модулю 3.

Решение Должно быть: f (0) = 0, f (1) = 0, f (2) = 0.

Перебором коэффициентов в выражении x2 + bx + c, находим подходящие многочлены:

–  –  –

По теореме Виета их произведение равно свободному члену, т.е. 1 2 1.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 53 / 78 Задачи с решениями

–  –  –





По теореме Виета их сумма равна коэффициенту перед x2186, т.е. 0.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 54 / 78 Задачи с решениями

–  –  –

F содержит 32 1 = 8 элементов и все они могут быть представлены как степени i, i = 1, 8 примитивного элемента.

Если элемент x окажется примитивным, то положим = x и, поскольку вычисления в F2 проводятся по mod a(x), будем иметь x2 + x + 2 = 0 x2 = x 2 = 2x + 1.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 55 / 78 Задачи с решениями

–  –  –

Заметим, что вычисление очередной степени i+j часто бывает удобным провести как i · j, а не как · i+j1.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 58 / 78 Задачи с решениями

–  –  –

Проведём умножение:

(x2 + x + 2) · (ax + b) = ax3 + (a + b)x2 + (2a + b)x + 2b.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 59 / 78 Задачи с решениями

–  –  –

с помощью расширенного алгоритма Евклида: им будет y(x).

Замечание: вычислять коэффициент при x4 + x3 + x2 + 3 (i (x)) нет необходимости.

ПРИКЛАДНАЯ АЛГЕБРА. Часть I: Конечные поля или поля Галуа. II 61 / 78 Задачи с решениями

–  –  –

Алгоритм заканчивает свою работу на Шаге 2, т.к. степень 0 очередного остатка r1 (x) = 3 равна степени многочлена в правой части (): 1 многочлен 0-й степени.

–  –  –

Т.к. как многочлен 6-ой степени h(x) не имеет делителей 3-й и меньших степеней, то он является неприводимым: если бы он имел делитель, скажем, степени 4, то у него был бы и делитель степени 6 4 = 2.

–  –  –

Найти минимальное поле характеристики 3, в котором многочлен f (x) = x3 + x + 2 F3 [x] раскладывается на линейные множители.

В данном поле найти все корни данного многочлена.

–  –  –

Построенное расширение поле F3 [x]/ x2 + 2x + 2 содержит найденный ранее корень 2, поэтому многочлен f (x) в этом поле раскладывается на следующие линейные множители:

–  –  –

Изоморфизм полей Галуа с одинаковым числом элементов.

Теорема о неприводимом нормированном многочлене делителе порождающего элемента идеала.

Циклическое пространство: определение и примеры.



Похожие работы:

«1 Содержание 1.ЦЕЛЕВОЙ РАЗДЕЛ 1.1. Пояснительная записка 1.2. Цель и задачи 1.3. Принципы и подходы в организации образовательного процесса 1.4. Характеристика особенностей развития детей седьмого года с общим недоразвитием речи 1.5. Характеристика основных компонентов речи детей 7-го года жизни с ОНР III-IV уровня ре...»

«Дополнительная общеобразовательная программа «Бумагопластика» Пояснительная записка Сегодня главной целью образования по-прежнему является всестороннее развитие и воспитание ребёнка. Но в XXI веке сама жизнь ставит перед нами новые задачи: формирование личности, способной преодолевать возникающие трудности, делать осознанный нр...»

«Применение Лигногумата на кукурузе 1. Предпосевная обработка семян*. Доза расхода препарата – 100 г марок А, АМ или 0,5 л марок Б, БМ на тонну семян. Обработка семян перед посевом при норме расхода рабочего раствора – 10 л/т семян. Рекомендуется совмещение с протравител...»

«СОДЕРЖАНИЕ: 1. Пояснительная записка.2. Принципы и подходы к формированию рабочей программы.3. Цели и задачи.4. Режим дня.5.Социальный паспорт семьи.6. Возрастные особенности детей.7. Годовые задачи.8. Перечень программ, технологий, пособий, используемых в группе.9. Особенности образовательного процесса в разно...»

«Муниципальное бюджетное образовательное учреждение средняя общеобразовательная школа № 2 города Рудни ПУБЛИЧНЫЙ ДОКЛАД ДИРЕКТОРА ШКОЛЫ (2014-2015учебный год) Рудня 2014-2015 1. Общая характеристика Муниципального бюджетного образовательного учреждения средней общеобразовательной школы №2 г.Рудни Муниципальное бю...»

«Кучина Ю.А. и др. Термическое разложение природных полисахаридов. УДК 541.64:547.458.81 Ю.А. Кучина, Н.В. Долгопятова, В.Ю. Новиков, И.Н. Коновалова, М.Ю. Принцева, В.А. Сагайдачный Термическое разложение природных полисахаридов: хитина и хитозана Yu.A. Kuchina, N.V. Dolgopyatova, V.Yu....»

««Ребята давайте жить дружно» Цели: развитие способности конструктивно вести себя в конфликтных ситуациях, расширение диапазона способов межличностного общения в микросоциальном окружении. Упражнение: «Встреча на узком мостике» Цель. Моделирование конфликтной ситуации, оценка предпочитаемого спо...»

«Глава 4. Методы и инструменты управления качеством 4.1. Структурирование функции качества (СФК) 4.1.1. Цели, области применения, эффективность и средства СФК Метод структурирования функции качества (СФК), которы...»

«Соглашение об оказании услуг «Триколор ТВ»1. Общие положения 1.1. Определение терминов, используемых в тексте Абонентского договора, раскрывается в Условиях оказания услуг «Триколор ТВ» и используется сторонами в целях толкования условий Абонентского договора.1...»

«Вестник ПСТГУ I: Богословие. Философия 2012. Вып. 5 (43). С. 33–46 ЭМПИРИЧЕСКИЙ ПОДХОД В ПРАКТИЧЕСКОМ БОГОСЛОВИИ (НА ПРИМЕРЕ РАБОТ Й. ВАН ДЕР ВЕНА) И. В. ЗАБАЕВ Термины «эмпирическое богословие» и «практическое богословие» не являются широко известными в нашей стране,...»








 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.