Материал: Статистическая теория систем. практикум. Володько А.В., Останков А.В

Если используют полиномы над полем GF(2), то есть коэффициенты при переменных являются элементами 0 и 1 этого поля и сложение их проводится по модулю два, то можно записать:

B(x)=A(x)+K(x)·P(x).

Для вычисления полинома В(x) , являющегося вычетом по модулю P(x) полинома A(x), надо к А(x) прибавить полином Р(x), умноженный на какой-то полином К(x) , который, выбирается так, чтобы степень В(x) была меньше степени полинома Р(x). Например, преобразование полинома x4+x можно провести следующим образом:

x4+x=x4+x+x(x3+x+1)=x2(mod(x3+x+1)), x4+x=x4+x+x(x3+x2+1)=x3+(x3+x2+1)=x2+1(mod(x3+x2+1)).

Если степень исходного полинома высокая, то обычно понижают ее постепенно, как это сделано в последнем примере.

При оперировании с полиномами над простым полем характеристики р для упрощения вычислений можно использовать соотношение (a+b)p=ap+bp,

при составлении табл. 3.5 (р=2) можно сразу написать для произведения (1+x+x2)·(1+x+x2)=1+x2+x4 и далее понижать степень, как было указано выше.

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

3.2.2. Мультипликативная структура конечных полей

Сначала введем понятие группы.

Группа - это множество элементов, для которых задана ассоциативная операция, имеется единичный элемент и для каждого элемента имеется обрат-

ный элемент. Если в группе определена операция сложения, то группа называется аддитивной. Если задано умножение - то мультипликативной. Группа,

имеющая конечное число элементов, называется конечной. Она обозначается как G(a, b, c,...). Число элементов в группе называется ее порядком.

В конечном поле можно выделить аддитивную и мультипликативную группы.

Все элементы любого конечного поля образуют аддитивную группу. Порядок аддитивной группы совпадает с порядком поля. Мультипликативная группа включает все элементы поля, кроме нулевого, поэтому ее порядок на I меньше порядка поля.

Наиболее интересна мультипликативная группа поля. Перейдем к ее рассмотрению.

Определение операции умножения на элементах поля означает, что если a GF(q) , то это поле должно содержать и a·a=a2 , a2·a=a3 и так далее. Иначе, по-

85

ле должно содержать все степени любого своего элемента. Должен существовать такой наименьший положительный показатель степени ε, что aε=1, тогда aε+k=ak и ε называется периодом элемента a. Все элементы ak, k 0, 1 , различны. Так как порядок мультипликативной группы поля GF(q) равен q-1, то максимально возможный период элемента поля

εmax=q-1. (51)

Если известен период ε произвольного элемента a поля GF(q), то можно определить период элемента ak, он будет равен ε/(ε,k), где (ε,k) - наименьший общий делитель чисел ε и k. Период ε любого ненулевого элемента поля GF(q) всегда делит порядок мультипликативной группы поля q-1: ε/q.

Элемент a, имеющий максимально возможный период εmax=q-1, называется первообразным элементом поля GF(q). Обозначим его через α. Степени α0, α1,…, αq-2 различны и пробегают все ненулевые элементы поля GF(q). Поэтому первообразный элемент является образующим элементом мультипликативной группы G поля GF(q):

Все k-е степени первообразного элемента αk также являются первообразными элементами этого поля, если k и q-1 взаимно простые числа, то есть, (k,q- 1) =1. Число чисел, взаимно простых с q-1 и не превосходящих q-1, определяется функцией Эйлера φ(q-1). Следовательно, в поле GF(q) имеется φ(q-1) перво-

образных элементов.

Элемент поля, мультипликативно обратный первообразному, тоже является первообразным.

Пример 3. Определить периоды элементов поля GF(7) и найти его первообразные элементы.

Поле GF(7)={ 0, 1, 2, 3, 4, 5, 6 } имеет мультипликативную группу G={ 1, 2, 3, 4, 5, 6 } порядка 6. Элементы этой группы могут иметь максимальный период εmах=6, а также меньшие периоды ε=1, 2, 3. Число элементов максимального периода, т.е. первообразных элементов, определяется функцией Эйлера φ(6)=2. Для определения периодов элементов поля составим табл. 3.6.

Таблица 3.6

Степени элементов a

86

Из таблицы видно, что первообразными элементами являются элемент 3 и обратный ему 5, имеющие максимальный период 6, совпадающий с порядком мультипликативной группы поля GF(7). Степени этих элементов пробегают все элементы мультипликативной группы, но в различной последовательности. Обращаем внимание на то, что период ε=3 также имеют два элемента: 2 и обратный ему 4 (см. пример 2). Периоды 1 и 2 имеют соответственно элементы 1 и 6, так как число чисел, взаимно простых с 1 и 2, равно 1.

В расширении любой степени m GF(рm) любого простого поля GF(p) все pm-1 элементов, отличных от 0, образуют циклическую мультипликативную группу, ее порядок pm-1: все элементы этой группы можно представить как различные степени первообразного элемента, или, как его еще называют, примитивного корня α. Степени αk, (k,pm-1)=1, также являются первообразными элементами расширенного поля GF(pm), их число равно φ(pm-1). Таким образом,

для любого расширенного поля GF(pm) существуют φ(pm-1) первообразных элементов.

Пример 4. Найти период элемента x поля GF(23) с неприводимым полиномом x3+x+1 (все возможные элементы мультипликативной группы этого поля приведены в первой строке табл. 3.1 и 3.2).

Запишем последовательные степени x и найдем их вычеты по модулю полинома x3+x+1: x0, x, x2, x3=x+1, x4=x2+x, x5=x2+x+1, x6=x2+1, x7=1. Видим, что

период элемента x равен εmax=7. Степени xk, k 1,6, пробегают все отличные от 0 элементы поля, следовательно, x является первообразным элементом поля. По-

казатели степени k первообразного элемента x, k 1,6, все являются взаимно простыми с периодом мультипликативной группы 7, поэтому все степени xk, k 1,6 являются первообразными элементами поля GF(23). Всего имеется φ(23- 1)=φ(7)=6 первообразных элементов.

Рассмотрим пример определения первообразных элементов расширенного поля

Пример 5. Определить первообразные элементы (примитивные корни) расширенного поля GF(24) с неприводимым полиномом x4+x+1.

Запишем последовательные степени x и найдем их вычеты по модулю полинома x4+x+1 (табл.3.2.4). Число первообразных элементов φ(15)=8. Элемент x является первообразным элементом расширенного поля GF(24), так как его пе-

риод равен pm-1=15. Первообразными элементами также являются x2, x4=x+1, x7= x3+x+1, x8=x2+1, x11=x3+ x2+x, x13=x3+x2+1, x14=x3+1, так как эти показатели

степеней x не имеют общих делителей с 15. Образующим элементом мультипликативной группы расширенного поля GF(24) может быть любой из приведенных первообразных элементов.

Но 3, 5, 6, 9, 10, 12-я степени первообразных элементов будут иметь меньший период и не будут первообразными элементами расширенного поля GF(24): 3, 6, 9 и 12-я степени любого первообразного элемента будут иметь период 15/3 =5, а 5 и 10-я - 15/5=3. Первообразные элементы расширенного поля обозначаются через α.

87

Таблица 3.7

xk и их вычеты по модулю полинома x4+x+1

Если в табл. 3.7 заменить x на α, то эта таблица будет верна для любого первообразного элемента, определенного выше: x2, x4, x7, x8, x11, x13, x14.

В мультипликативной группе можно выделить подгруппы, если в группе имеются элементы, период которых меньше εmax. Подгруппа g - это часть группы, которая обладает свойствами группы, то есть в ней определена ассоциативная групповая операция, имеется единичный элемент и для каждого элемента обратный.

Например, для расширенного поля GF(24) , элементы которого приведены

в табл.1.4., подгруппами могут быть множества элементов: x0=1, x5=x2+x, x10=x2+x+1 (период 3) и x0 =1, x3, x6=x3+x2, x9=x3+x (период 5).

Пример 6. Определить все подгруппы мультипликативной группы, поля

GF(7).

Воспользуемся результатами примера 3. Образующими элементами мультипликативных подгрупп могут быть 1, 2, 4, 6. Эти элементы имеют период, меньший εmax=6. Подгруппы с образующими 2 и 4 имеют одни и те же элементы. Таким образом, в мультипликативной группе поля GF(23) можно выделить 3 мультипликативные подгруппы:

g1={ 1 }, g2={ 1, 2, 4 }, g3={ 1, 6 }.

Здесь следует заметить, что мультипликативная группа поля GF(23), рассмотренная в примере 1.4, не имеет подгрупп, так как все ее элементы имеют максимальный период, являются первообразными элементами.

88

Введем понятие смежных классов. Пусть G={ a1, a2,…} - мультиплика-

тивная группа и g={ g1, g2,… } - ее подгруппа. Тогда множество элементов вида a·gi, где gi принимает значения из g и a - фиксированный элемент G, называ-

ется смежным классом по g и обозначается ag. Из определения следует, что смежный класс по g и подгруппа g содержат одинаковое число элементов. Кро-

ме того, если у двух классов оказался общий элемент, то они совпадают. Эле-

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

Группу G можно представить как объединение непересекающихся смежных классов

G={a1g}+{a2g}+…+{akg}. (52)

Здесь символ сложения следует рассматривать как символ объединения. Представление (1.3) называется разложением группы на смежные классы.

Пример 7. Представить разложение на смежные классы мультипликативной группы поля GF(7).

Из решения примера 1.6 можно взять подгруппы { 1, 6 } и { 1, 2, 4 }, по которым можно разложить мультипликативную группу на смежные классы. Первую подгруппу, состоящую из одного элемента { 1 }, брать нет смысла, так как смежные классы будут состоять из одного элемента.

Следует пояснить образование смежных классов (образующим элементом является 1). При определении других смежных классов в качестве образующих элементов выбирают элементы поля, которые не входят ни в один из уже определенных смежных классов.

Рассмотрим смежные классы по подгруппе g={ 1, 6 }. Одним из смежных классов является подгруппа { 1.6 } (её элементы умножены на 1 - первый элемент мультипликативной группы). Второй смежный класс получим умножением элементов подгруппы { 1, 6 } на 2 - второй элемент группы: { 2·1, 2·6 }={ 2, 5 }, Третий смежный класс получим умножением элементов подгруппы {1,6} на 3 – третий элемент группы: { 3·1, 3·6 }={ 3,4 }. Дальнейшее умножение на элементы группы 4, 5, 6 проводить не будем, так как эти элементы уже входят в определенные смежные классы. Таким образом получим смежные классы по подгруппе { 1, 6 }: { 1, 6 }, { 2, 5 }, { 3, 4 }. Тогда мультипликативную группу G={ 1, 2, 3, 4, 5, 6 } можно представить в виде

G={ 1, 6 }+{ 2, 5 }+{ 3, 4 }.

Рассмотрим подгруппу {1, 2, 4 }, смежные классы по этой подгруппе { l, 2, 4 } и { 3, 6, 5 }. Следовательно, G(1, 2, 3, 4, 5, 6)={ 1, 2, 4 }+{ 3, 6, 5 }.

Пример 8. Представить разложение на смежные классы мультипликативной группы расширенного поля GF(24) c неприводимым полиномом x4+x+1.

Элементы мультипликативной группы расширенного поля GF(24) будем

представлять степенями первообразного элемента α. Мультипликативную группу поля можно представить в виде степеней α0, α1, α2, α3, α4, α5, α6, α7, α8, α9, α10, α11, α12, α13, α14.

89