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

Порядок мультипликативной группы 15. Подгруппы могут иметь порядок 3 или 5. Выберем подгруппу порядка 5: α0, α3, α6, α9, α12. В табл.3.8 приведены смежные классы мультипликативной группы поля GF(24) по рассматриваемой подгруппе (элементы поля представлены степенями примитивного элемента αk, а также вычетами по модулю неприводимого полинома x4+x+1.

Таблица 3.8

Смежные классы расширенного поля GF(24)

3.2.3. Алгебраическая структура полей Галуа

Будем рассматривать расширенные поля Галуа, элементы которых представляются алгебраическими выражениями. Различные представления элементов поля Галуа приведены в табл. 3.9 для частного случая GF(24) с неприводимым полиномом x4+x+1.

Как было определено в примере 5, элементы мультипликативной группы поля GF(24) имеют периоды: 15, 5 и 3. В общем случае любой элемент α мультипликативной группы поля GF(рm), имеющий период ε, удовлетворяет сравнению

αε≡1 (53)

Первообразный элемент α имеет максимальный период ε=pm-1 и, следовательно,

90

С другой стороны, известно, что полином xpm -x можно представить в виде произведения неприводимых полиномов, то есть таких, которые не представляются в виде произведения полиномов меньшей степени над простым полем GF(р), для которых элементы поля GF(р) не являются корнями. Однако в расширенном поле GF(рm) неприводимые над полем GF(р) полиномы уже имеют корни, то есть могут обращаться в 0.

Какие-то k элементов расширенного поля GF(рm) будут корнями только одного неприводимого над полем GF(p) полинома степени k, при этом k должно делить m. Если α является корнем неприводимого полинома k -й степени, то остальными (k-1) корнями будут

Элементы (58) называются р-сопряженными с α.

Неприводимые полиномы степени m, которые делят xpm 1 1, но не делят никакой двучлен меньшей степени, называются примитивными полиномами. Корни именно этих полиномов имеют максимальный период рm-1 и называются примитивными элементами. По-другому примитивный элемент называют примитивным корнем, так как он определяется как корень степени рm-1 из 1 (в соответствии с формулой (58)). Число примитивных элементов определяется

91

функцией Эйлера φ(рm-1), а число примитивных полиномов в m раз меньше - φ(pm-1)/m, так как каждый примитивный полином имеет m различных корней. В разложении полинома xpm 1 1 на множители могут встречаться и другие полиномы степени m, но они не будут примитивными, хотя и будут неприводимыми над полем GF(р). В разложении могут встречаться неприводимые полиномы любой степени k, которая делит m: k│m. Сумма степеней всех полиномов должна равняться рm-1. Например, для поля GF(24)

x16+x=x·(x+1)(x2+x+1)(x4+x3+x2+x+1)(x4+x+1)(x4+x3+1).

Все полиномы в этом разложении являются неприводимыми над полем GF(2), но только два последних являются примитивными в поле GF(24). Полином x4+x3+x2+x+1 не является примитивным, так как делит без остатка x5+1: (x5+1)/(x4+x3+x2+x+1)=x+1. Степени полиномов могут быть 1, 2 и 4, так как они должны делить m=4.

В общем случае корни полинома степени k будут иметь период, который определяется как наименьшее значение степени n, при которой двучлен xn-1 делится на этот полином без остатка. Так, полином x+1 делит x+1, следова-

тельно, период элемента, являющегося корнем полинома x+1=0, равен 1. Полином x2+x+1 делит без остатка x3+1, следовательно, его корни имеют период 3, а корни полинома x4+x3+x2+x+1 имеют период 5. Примитивные полиномы x4+x+1 и x4+x3+1 делят без остатка только x15+1, их корни имеют максимальный пери-

од 15.

Элементы поля, являющиеся корнями одного полинома, называются со-

пряженными. Все элементы поля можно распределить на классы эквивалентности (сопряженности), в каждом классе объединяются сопряженные элементы. Классы сопряженности обозначим через Аi , где индекс i определяется показателем степени примитивного элемента, входящего в этот класс. Например, для поля GF(24) будут следующие классы сопряженности:

A0 (α0 ), A1(α1, α2, α4 , α8 ), A7 (α7, α14, α13, α11), A3 (α3, α6 , α12 , α9 ), A5(α5, α10 ).

Рассмотрим подробнее объединение элементов мультипликативной группы поля GF(24) в классы сопряженности.

Пример 9. Определить классы сопряженных элементов мультипликативной группы поля GF(24).

Обозначим, как и прежде, через α какой-то первообразный элемент поля

GF(24), который теперь будем называть примитивным. Предположим: α явля-

ется корнем примитивного полинома x4+x+1.

Корнями этого же полинома так же будут α2, α4, α8, всего 4 корня. Второй примитивный полином является обратным первому, то есть коэффициенты при xi в первом полиноме будут коэффициентами при xm-i во втором, обратном, полиноме. Корнями второго полинома будут элементы мультипликативной

92

группы, обратные корням первого полинома, то есть α14, α13, α11, α7. Напомним, что в мультипликативной группе обратный элемент ā=a-1, так, если a=α2, то ā=α-2=α15-2=α13. Осталось определить корни не примитивных полиномов. Полином x+1 будет иметь корнем элемент α0=1, а полином x2+x+1 элемент периода 3, Используя результаты решения примера 1.5, получим корни этого полинома α5 и α10. Из того же примера можно получить корни полинома x4+x3+x2+x+1 (период этих элементов 5): α3, α6, α9, α12 . Таким образом, для мультипликативной группы поля GF(24) имеем классы сопряженности А0, А1, А7, А3, А5, которые были указаны выше. В классах сопряженности элементы могут быть представлены и полиномами степени ниже m=4, а также двоичными полиномами. Эти представления элементов поля GF(24) можно взять из табл. 3.9. Классы сопряженных элементов тогда будут представлены следующим образом:

A0 (1), A1(α, α2 , α 1, α2 1), A7 (α3 α2, α3 +1, α3 +α2 +1, α3 +α2 +α), A3 (α3 , α3 +α2, α3 +α2 +α+1, α2 +1), A5 (α2 +α, α2 +α+1)

или

А0(1), A1(0010,0100,0011,0101), A7(1011,1001,1101,1110), A3(1000,1100,1111,0101), A5(0110,0111).

Выводы по разделу.

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

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

2.Элементами простого поля GF(р) являются целые числа по модулю простого числа р. Элементами расширенного поля GF(рm) степени m являются полиномы степени не выше m, являющиеся вычетами по модулю неприводимого над полем GF(p) полинома.

3.Группа - это множество элементов, для которых задана одна ассоциативная операция, имеется единичный элемент и для каждого элемента обратный. В конечном поле можно выделить аддитивную и мультипликативную группы. Порядок аддитивной группы (число ее элементов) совпадает с порядком поля, а мультипликативной - на 1 меньше. Все элементы мультипликативной группы можно представить степенями какого-то элемента. Этот элемент поля называется первообразным. В группе можно выделить подгруппу, все элементы которой можно представить степенями элемента, образующего подгруппу (он не является первообразным элементом). Порядок подгруппы делит порядок группы. Все элементы группы могут быть распределены на смежные классы по какой-то подгруппе, элементами которых является результат умножения элементов подгруппы на элементы группы.

93

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

3.2.4.Задания для самопроверки

1.Записать конечные поля характеристик р=3, 5, 7. Для каждого из этих

полей:

а) записать аддитивную и мультипликативную группы, указать их поря-

док;

б) записать таблицу степеней элементов мультипликативной группы, определить порядок каждого элемента;

в) определить образующие элементы мультипликативных подгрупп, определить их порядок, записать подгруппы мультипликативной группы;

г) определить смежные классы мультипликативной группы по каждой подгруппе, представить мультипликативную группу как объединение непересекающихся смежных классов.

2.Для расширенных полей GF(23), GF(24), GF(25) определить число примитивных элементов (с использованием функции Эйлера) и степени неприводимых полиномов.

3.В поле GF(23) для примитивного полинома x3+x+1 составить таблицу

последовательных степеней примитивного элемента α в виде: степеней примитивного элемента αi , i=0,7, полиномов степени, меньшей 3 (использовать, что α является корнем примитивного полинома α3+ α+1=0), двоичных полиномов.

3.3. Поля Галуа и псевдослучайные последовательности

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

физмом.

Рассматривая псевдослучайные последовательности как сигналы для РТС передачи информации, следует отметить их важнейшую характеристику - корреляционные функции. В этой главе приводятся корреляционные свойства двоичных последовательностей, необходимые и достаточные условия для получения одноуровневой корреляционной функции с заданным значением выбросов.

94