Как построить поле галуа

Как выбрать цель

Поле Галуа. Определение .Генерация поля

Поле Галуа. Определение .Генерация поля

Теорема 6.13. Пусть p ( x ) — многочлен с коэффициентами из поля F = GF ( q ).

Алгебра многочленов над полем F по модулю p ( x ) является полем тогда и только тогда , когда многочлен p ( x ) — неприводим в поле F , т.е. если p ( x ) нельзя представить в виде произведения многочленов с коэффициентами из F .

Поле, образованное многочленами над полем F (т.е. c коэффициентами из этого поля) по модулю неприводимого многочлена p ( x ) степени m , называется расширением поля степени m над F , т.е. GF ( q m ) .

Первоначальное поле F называется основным полем. Поле много –

( изоморфный – сходный по форме)

Поля Галуа, которые могут быть образованы многочленами по модулю неприводимого многочлена над полем GF ( p ), называются полями характеристики p . Таким образом, при любом выборе m поле GF ( p m ) — это поле характеристики p .

Теорема 6.14. В поле характеристики p имеет место равенство ( a + b ) p = a p + b p .

Конечные поля GF(p m ) порядка p m , где характеристика p – простое число, а размерность m — натуральное число, порождаются с помощью неприводимых полиномов степени m. Особенно удобно использовать примитивные неприводимые полиномы F (x) ; в этом случае простое поле GF(p) может быть расширено до поля GF(p m ) за счёт присоединения корня α полинома F ( x ).

В таблице 11 представлены примитивные неприводимые полиномы характеристики 2 (до степени m =10) с коэффициентами из простого поля GF(2), а также полиномы характеристик 3, 5, 7 малых степеней. Впрочем, с математической точки зрения выбор полина не существенен, так как все конечные поля одного и того же порядка изоморфны.

Введение

Вычисления над кольцами и в простых полях

Алгебраические системы — это системы, которые подчиняются определённым правилам или законам. В большей части это те же законы, которые приложимы к обычным числовым системам. Так группа — система в которой заданы одна основная операция и операция ей обратная, например сложение и вычитание или умножение и деление. В кольце определены две основные операции. Сложение и умножение и операция обратная первой (вычитание). В поле определены две основные операции и две обратные операции.

Алгебраическая группа

Группой называется совокупность объектов или элементов, для которых определена некоторая операция и выполняются аксиомы G1-G4. Операцию обычно называют сложением или умножением, даже если она не является арифметическим сложением или умножением

G1 (замкнутость) Операция может быть применена к любым двум элементам группы, в результате получается третий элемент группы.

G2 (ассоциативный закон) Для любых трёх элементов a, b, c группы (a+b)+c = a+(b+c) для сложения или (ab)c=a(bc) для умножения.

G3 Существует единичный элемент. Для сложения a+0=a или для умножения a´1=a

G4 Каждый элемент группы имеет обратный

Если кроме аксиом G1-G4 выполняются условие коммутативности или a+b=b+a то группу называют коммутативной или абелевой.

Алгебраическое кольцо

Кольцом R называется множество элементов над которым определены две операции. Одна называется сложением, а вторая умножением, даже если эти операции не являются обычным арифметическим сложением и умножением чисел. Для того чтобы множество R было кольцом должны выполняться следующие аксиомы:

R1 Множество R является абелевой группой относительно операции сложения

R2(замкнутость) Для любых двух элементов a и b из множества R определено произведение ab, которое является элементом R

R3(ассоциативный закон) Для любых трёх элементов a, b, с из множества R выполняется a(bc)=(ab)c

R4(дистрибутивный закон) Для любых трёх элементов a, b, с из множества R выполняется a(b+c)=ab+ac и (b+c)a=ba+ca.

Кольцо называется коммутативным, если коммутативна операция умножения, т. е. если для любых двух элементов a и b из множества R ab=ba

Поле Галуа

Полем называется коммутативное кольцо с единичным элементом относительно умножения в котором каждый не нулевой элемент имеет обратный элемент по умножению.

Поля в которых определена операция сложения и умножения по модулю простого числа называются простыми полями. Для другого количества элементов поля существуют не всегда.

Особенности вычислений в простых полях Галуа

В результате вычислений искомый результат находится в пределах 0£d b )³c, то d приравнивается к остатку от целочисленного деления результата (a b ) на c

При возведении в степень область значений степенной функции в поле Галуа или над кольцом может быть меньше, чем область значений аргументов степенной функции

Извлечение дискретного логарифма

Операция дискретного логарифмирования определена как операция обратная возведению в степень. Найти обозначает найти такое число d, что при возведении a в эту степень получим число b.

В результате вычислений искомый результат находится в пределах 0£d

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Как то на паре, один преподаватель сказал, когда лекция заканчивалась — это был конец пары: "Что-то тут концом пахнет". 8410 — | 8028 — или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)
очень нужно

Решеткой называют алгебраическую структуру, заданную конечным множеством M с двумя бинарными операциями.

— решетка.

Отношение является отношением частичного порядка.

Множество M с отношением частичного порядка называется упорядоченным множеством.

Для графического представления упорядоченного множества используют диаграмму Хассе.

Каждому элементу ставится в соответствие точка на плоскости, причем если выполняется соответствие , точку, соответствующую элементу a, располагают ниже точки, соответствующей элементу b.

Точки a и b соединены линией или ребром, если

Пусть имеется отношение порядка

Диаграмма Хассе помогает лучше понимать взаимосвязь элементов, принадлежащих одному и тому же упорядоченному множеству.

Дистрибутивная решетка.

Решетка называется дистрибутивной решеткой, если для всех элементов, принадлежащих множеству M, выполняется условие:

1)

2)

Диаграмма Хассе для дистрибутивной решетки

Булева алгебра.

Булева алгебра — ограниченная дистрибутивная решетка, в которой имеется унарная операция дополнения на множестве М такое, что

;

.

Тема 5. Поля Галуа и их применение. Классическая теория Галуа. Расширения полей и их классификация. Сепарабельные и нормальные расширения. Расширения полей q, f_q, c(t).

5.1 Поля Галуа и их применение

Полеммы называем непустое множествоPкомплексных чисел, обладающее следующими свойствами:

если и, тои;

если , то—и(при).

Полями являются, например, поле рациональных чисел R, поле действительных чиселD, поле комплексных чисел С.

Поле Галуаили Конечное поле — поле, состоящее из конечного числа элементов. Конечное поле обычно обозначаетсяили GF(q), где q — число элементов поля. Простейшим примером конечного поля является—кольцовычетов по модулюпростого числа.

Характеристикаконечного поля являетсяпростымчислом.

Число элементов любого конечного поля есть его характеристика в натуральной степени: .

Для каждого простогочисла p инатуральногоn существует конечное поле из q = pn элементов, единственное с точностью доизоморфизма. Это поле изоморфно полюразложениямногочлена.

В каждом поле существует по крайней мере один примитивный элемент α, то есть такой, что . Любой ненулевой элемент β является некоторой степенью примитивного элемента:.

Мультипликативнаягруппаконечного поляявляетсяциклической группойпорядка q − 1. Поэтому, в частности, в конечном поле всегда существует примитивный элемент α, порядок которого равен q − 1, то есть αq − 1 = 1 идля 0

Пусть надо построить поле GF(9) = GF(32). Для этого необходимо найти многочлен степени 2, неприводимыйв. Такими многочленами являются: x 2 + 1

Возьмём, например, x2 + 1, тогда искомое поле есть . Если вместо x2 + 1 взять другой многочлен, то получится новое поле, изоморфное старому.

Таблица сложения в GF(9)

Таблица умножения в GF(9):

5.2 Классическая теория Галуа

Тео́рия Галуа́— разделалгебры, изучающий симметрии корнеймногочленов. Симметрии описываются в терминахгруппы перестановоккорней многочлена (группа уравнения) — термин, впервые использованныйЭваристом Галуа

Созданная Э. Галуа теория алгебраических уравненийвысшихстепеней с одним неизвестным, т. е. уравнений вида

устанавливает условия сводимости решения таких уравнений к решению цепи др. алгебраических уравнений (обычно более низких степеней). Т. к. решением двучленного уравнения xm= Аявляется радикал,то уравнение (*) решается в радикалах, если его можно свести к цепи двучленных уравнений. Все уравнения 2-й, 3-й и 4-й степеней решаются в радикалах. Уравнение 2-й степениx 2 + px + q = 0было решено в глубокой древности по общеизвестной формуле

уравнения 3-й и 4-й степеней были решены в 16 в. Для уравнения 3-й степени вида x 3 + px + q = 0(к которому можно привести всякое уравнение 3-й степени) решение даётся т. н. формулой Кардано: