Как построить поле галуа
Содержание
Как выбрать цель
Поле Галуа. Определение .Генерация поля
Поле Галуа. Определение .Генерация поля
Теорема 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-й степени) решение даётся т. н. формулой Кардано:
опубликованной Дж. Карданов 1545, хотя вопрос о том, найдена ли она им самим или же заимствована у др. математиков, нельзя считать вполне решенным. Метод решения в радикалах уравнений 4-й степени был указан Л.Феррари.
В течение трёх последующих столетий математики пытались найти аналогичные формулы для уравнений 5-й и высшихстепеней. Наиболее упорно над этим работали Э.Безуи Ж.Лагранж. Последний рассматривал особые линейные комбинации корней (т. н резольвенты Лагранжа), а также изучал вопрос о том, каким уравнениям удовлетворяют рациональные функции от корней уравнения (*). В 1801 К.Гаусссоздал полную теорию решения в радикалах двучленного уравнения видаxn= 1, в которой свёл решение такого уравнения к решению цепи двучленных же уравнений низших степеней и дал условия, необходимые и достаточные для того, чтобы уравнениеxn= 1 решалось в квадратных радикалах. С точки зрения геометрии, последняя задача заключалась в отыскании правильных n-угольников, которые можно построить при помощи циркуля и линейки; поэтому уравнениеxn= 1 и называется уравнением деления круга. Наконец, в 1824 Н.Абельпоказал, что общее уравнение 5-й степени (и тем более общие уравнениявысшихстепеней) не решается в радикалах. С другой стороны, Абель дал решение в радикалах одного общего класса уравнений, содержащего уравнения произвольно высоких степеней, т. н. абелевых уравнений.
Т. о., когда Галуа начал свои исследования, в теории алгебраических уравнений было сделано уже много, но общей теории, охватывающей все возможные уравнения вида (*), ещё не было создано. Например, оставалось: 1) установить необходимые и достаточные условия, которым должно удовлетворять уравнение (*) для того, чтобы оно решалось в радикалах; 2) узнать вообще, к цепи каких более простых уравнений, хотя бы и не двучленных, может быть сведено решение заданного уравнения (*) и, в частности, 3) выяснить, каковы необходимые и достаточные условия для того, чтобы уравнение (*) сводилось к цепи квадратных уравнений (т. е. чтобы корни уравнения можно было построить геометрически с помощью циркуля и линейки). Все эти вопросы Галуа решил в своём «Мемуаре об условиях разрешимости уравнений в радикалах», найденном в его бумагах после смерти и впервые опубликованном Ж. Лиувиллем (См. Лиувилль) в 1846. Для решения этих вопросов Галуа исследовал глубокие связи между свойствами уравнений и групп (См.Группа) подстановок, введя ряд фундаментальных понятий теории групп. Своё условие разрешимости уравнения (*) в радикалах Галуа формулировал в терминах теории групп. Г. т. после Галуа развивалась и обобщалась во многих направлениях. В современном понимании Г. т. — теория, изучающая те или иные математические объекты на основе их групп автоморфизмов (так, например, возможны Г. т. полей, Г. т. колец, Г. т. топологических пространств и т. п.).
Расширение полей и их классификация
Расшире́ние Галуа́ — алгебраическое расширение поляEÉ K, являющеесянормальнымисепарабельным. При этих условиях E будет иметь наибольшее количествоавтоморфизмовнад K (если E -конечно, то количество автоморфизмов также конечно и равно степени расширения [E:K]).
Группа автоморфизмов E над K называется группой Галуа и обозначается Gal(E/K) (или G(E/K)).
Если Gal(E/K) абелева,циклическаяи т.д., то расширение Галуа называется соответственно абелевым, циклическим и т.д. соответственно.
Иногда рассматривают группу Галуа для расширения E, которое сепарабельно, но необязательно нормально. В этом случае под группой Галуа E/K понимают группу Gal(Ē/K), где Ē — минимальное нормальное расширение K, содержащее E (в конечном случае, когда сепарабельное расширение является простым E=K(α) для некоторого α, являющегося корнем неприводимогонад K многочлена f(x), Ē являетсяполем разложенияэтого многочлена).
Согласно определению, полем называется множество, на котором заданы операции сложения и умножения, причём выполняются групповые аксиомы (см. теорию групп; должно быть обеспечено выполнение переместительного закона сложения и умножения, наличие нейтральных элементов относительно сложения и умножения).
Говоря обычным языком, для любых элементов должны выполняться равенства a+b=b+aиa*b=b*a. И должен существовать такой элемент е, принадлежащий нашему множеству (полю), что для всех элементов множестваaвыполняетсяa=a+e, и такой элементu, чтоa=a*u. Для обычного сложенияe=0, аu=1.
Однако, умножение и сложение, которые определены для полей, могут не иметь ничего общего с обычным сложением или умножением (кроме выполнения вышеупомянутых законов).
Полями Галуа называются поля, в которых присутствует конечное число элементов. Поле Галуа с количеством элементов NобозначаетсяGF(N).
Определим сложение, как операцию «исключающее ИЛИ» (XOR). Очевидно, что в таком случае, операция сложения является обратной самой себе. Операция умножения в двоичном виде будет выглядеть так
Т.е. обычное умножение «столбиком» со сложением определённым как XOR.
Такую операцию часто представляют как умножение полиномов. (x+1)*(x+1) =x 2 +1
Можно определить также операцию деления чисел (или полиномов) с остатком — по аналогичным правилам, например:
Число 11011000 (или полином x 7 +x 6 +x 4 +x 3 ) является остатком от деления.
Теперь рассмотрим поле Галуа, состоящее из 2 4 = 16 элементов. Операция сложения для этого поля определена какXOR, операция же умножения дополнена получением остатка по некоторому модулю.
Выберем в качестве модуля полином x 4 +x+1 (т..е число 10011).
Возьмём единицу и будем последовательно умножать её на 2 и рассмотрим числа, которые будут при этом получаться: (рассмотрим двоичную форму и представление в виде полинома)
1 = 2 0 = 0001 = x 0
2 0 *2 = 2 1 = 0010 mod 10011 =2 = x 1
2 1 *2 = 2 2 = 0100 mod 10111 =4 = x 2
2 2 *2 = 2 3 = 1000 mod 10011= 8 = x 3
Эти три строки повторяют обычное умножение, однако дальше всё не так просто
2 4 *2 = 2 4 = 10000 mod 10011 = 0011 = 3 = x+1
2 4 *2 = 2 5 = 100000 mod 10011 = 0110 = 6 = x 2 +x