Поля Галуа и их свойства

Конечное поле, называемое именем французского математика Галуа и обозначаемое GF(q), представляет собой конечное мно­жество, состоящее из q элементов, обладающих свойствами по­ля. Число элементов поля q является простым числом или сте­пенью простого числа. В первом случае имеем простое поле, а во втором — расширение простого поля. Если q — простое чис­ло, то элементами поля GF (q) с характеристикой q являются числа 0, 1, 2,... (q — 1). При этом в соответствии со свойства­ми поля сложение и умножение элементов такого поля осуще­ствляется с приведением по модулю q.

где все коэффициенты аⁱ- пробегают полную систему вычетов по модулю р, т. е. принадлежат простому полю GF (р). Сложение двух элементов

Если q является степенью простого числа р, т. е. q = р^т, где т — целое, то элементами поля GF(p^m) будут многочлены степени (т — 1) вида

производится с приведением коэффициентов по модулю р. Тогда элемент С = с₀+с_1{х + с₂х²... + c_m-1x^m-1 будет суммой двух элементов А и В, т. е. С = А+В, где с_i= (a_i + b_i )(тоdр).

Для умножения двух элементов поля А и В перемножим их алгебраически как многочлены независимой переменной х. затем найдем остаток D от деления произведения А-В на не­который специальный многочлен р (х) степени т с коэффици­ентами, принадлежащими простому полю GF (р). Этот много­член должен обладать тем свойством, что его нельзя разло­жить на множители, используя только многочлены с коэффи­циентами из простого поля GF (р). Такой многочлен называ­ют неприводимым. Тогда полученный остаток D с коэффициен­тами, принадлежащими простому полю GF (р), можно рассмат­ривать как вычет по двойному модулю — по mod p и mod P (х), т. е. А*В≡D[mod р, Р (х)]. При таких правилах сложения и умножения совокупность рассматриваемых элементов и об­разует конечное поле Галуа.

Многочлены Р (х) и элементы поля GF(p'ⁿ) обладают це­лым рядом свойств, используемых при построении и описании циклических кодов. Приведем основные из этих свойств, дока­зательство которых можно найти в курсах Высшей алгебры и в ряде монографий по теории корректирующих кодов, напри­мер [1,3, 4].

Cвойство 1.1. В се отличные oт нуля элементы поляGF(p^m)образуют мультипликативную группу порядка р^т —1. Тогда для любого элемента поля а имеет место равенство а^{р^m -1}=1.

Вытекающее из этого свойства равенство а^{р^m} = а выполня­ется также и для нулевого элемента поля а = 0. Очевидно, что ненулевые элементы поля являются корнями многочлена

х^{р^m -1}-1 =I, а все элементы поля являются корнями многочлена x^{p^m}-x

Свойство 1.2. В поле GF (p^m) всегда существует первообраз­ный элемент а, т. е. элементпорядка р^m — 1. Каждый ненуле­вой элемент поля может быть представлен как некоторая сте­пень одного и того же первообразного элемента а. Иными сло­вами: мультипликативная группа поля Галуа циклична.

В теории циклических кодов играет важную роль следующее свойство:

Свойство 1.3. Всякий приводимый по модулю р многочлен Р (х) степени m, если он существует, есть делитель по этому модулю двучлена х^{р^m- 1} -1.

Примитивным называется такой неприводимый по модулю р многочлен Р (х) степени т, корни которого являются первооб­разными элементами поля GF(p^m), т. е. имеющими порядок р^m — 1.

Порядок корней неприводимого многочлена называют пока­зателем, к которому этот многочлен принадлежит. Если непри­водимый многочлен принадлежит показателю k, то он является делителем двучлена х^к — 1, но не является делителем двучле­нов вида хⁿ — 1, где п < k. Следовательно, неприводимый мно­гочлен Р (х) степени т является примитивным тогда и только тогда, когда он принадлежит показателю р^т — 1.

Приведем теперь три свойства, которые позволяют опреде­лить элементы поля, являющиеся корнями многочлена Р (x), если известно, что один из этих корней а.

Свойство 1.4. В простом поле G F (p) имеет место равен­ство (а +b)^р = а^p + b^p.

Свойство 1.5. Для простого модуля р справедливо сравнение

где Р (х) — произвольный многочлен, коэффициенты которого принадлежат простому полю GF (р).

Свойство 1.6. Если элемент а поля GF (p^m) есть корень не­приводимого по модулю р многочлена Р (х) степени т, то остальными корнями Р (х) будут элементы a^p, a^{p^2},…a^{p^(m-1)}.

Важную роль в теории циклических кодов играют следую­щие два свойства:

Свойство 1.7. Многочлен x^k-1 является делителем много­члена х^п — 1, если k — делитель п.

Свойство 1.8 Если неприводимый по модулю р многочлен Р₁(х) степени k является делителем двучлена х^p-1, то степень k должна быть делителем числа т. И наоборот: всякий неприводимый по модулю р многочлен Р₁ (х), степень которого k есть делитель числа т, будет делителем по модулю р двучлена х^{p^m-1}-1.

Свойство 1.9. Для любого простого числа р и любого примитивного многочлена Р (х) степени m существует только одно поле Галуа GF (p^m), иными словами, поля Галуа GF (р^т), об­разованные различными неприводимыми примитивными много­членами степени т, изоморфны.

В заключение этого параграфа рассмотрим пример постро­ения поля GF (р'^п).

Пример. Пусть требуется построить поле Галуа GF (р^т), где р = 2, а т = 4, т. е. GF(2⁴). Поле должно представлять собой совокупность многочленов, несравнимых с нулем по двой­ному модулю [mod р, Р (х)]. По свойству 1.9 для построения поля Галуа GF (2⁴) может быть выбран любой примитивный многочлен Р (х) степени т = 4.

Для нахождения примитивных многочленов можно восполь­зоваться таблицами, приведенными в [1, 4].

Выберем в качестве Р (х) неприводимый по модулю 2 при­митивный многочлен х⁴ + х + 1. Пусть а является корнем дан­ного многочлена, тогда он будет первообразным элементом по­ля GF (2⁴). По свойству 1.2 все 15 ненулевых элементов поля будут следующими (все степени а приводятся по modP(x):

Таблица 1.1

Заметим, что элементы поля могут быть представлены как век­торы, компонентами которых являются коэффициенты соответ­ствующих многочленов.

Дата добавления: 2015-07-16