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

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

Задание операций сложения и умножения означает, что если элементы a и b принадлежат полю G (a G и b G), то a+b G и a·b G. Единичный элемент е определяется выражением a*e=a, где композиция * означает сложение или умножение. Единичный элемент относительно операции умножения есть «1», а относительно операции сложения – «0». Понятие обратного элемента ā вытекает из равенства a*ā=e. О нем есть смысл говорить относительно операции умножения a·ā =1, то есть ā=-a-1. Относительно операции сложения обратным элементом ā является элемент -a, что вытекает из равенства a+ā =0 (0 - единичный элемент относительно сложения).

Примерами полей являются:

-поле действительных чисел Q,

-поле рациональных чисел R,

-поле комплексных чисел С.

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

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

Конечное поле - поле, содержащее конечное число элементов. Конечные поля называются полями Галуа по имени их первого исследователя Эвариста Галуа.

Число элементов в поле называется его порядком. Приведенные выше в качестве примера поля действительных, рациональных и комплексных чисел имеют бесконечный порядок. Число элементов любого поля Галуа (его порядок) есть степень рm некоторого натурального простого числа р, являющегося характеристикой этого поля. Для любого натурального простого числа р и любого натурального m существует поле из рm элементов. Его обозначают GF(рm). Поле GF(рm) содержит в качестве подполя GF(рn) в том и только в том случае, если m делится на n, что обозначается n│m – n делит m.

Пример 1. В поле GF(24) существуют два подполя GF(2) и GF(22).

B любом поле GF(рm) содержится подполе GF(p), называемое простым полем характеристики р (р - простое число).

Поле GF(рm) называется расширением простого поля GF(P), так как расширенное поле - это поле, содержащее данное поле в качестве подполя.

Так, в соответствии с примером 1.1 поле GF(24) можно рассматривать как расширение полей GF(2) или GF(22). Из этих двух полей первое является простым полем характеристики 2, а второе, в свою очередь, может рассматриваться как расширение простого поля GF(2).

Элементами простого поля являются целые числа по модулю простого числа р.

80

Здесь надо пояснить, как вычисляется число по модулю и что такое вычеты. Для этого надо использовать теорию сравнения целых чисел [22].

Сравнение целых чисел a и b по модулю k (k - любое целое положительное число) записывается в виде a≡b(mod k), оно эквивалентно равенству a- b=r·k, то есть b можно рассматривать как остаток от деления a на модуль k (r - целое число). Так

2=0 mod 2, 15=5 mod 10, 23=2 mod 7, -2=5 mod 7, -23=2 mod 7.

Все целые числа a такие, что a≡b(mod k) при фиксированном b образуют класс чисел по модулю k, который обозначается, через { b } или b(mod k). Всем числам этого класса соответствует один и тот же остаток b, и можно получить все числа класса (их количество бесконечно), если в формуле b+r·k заставить r пробегать все целые числа (положительные и отрицательные). Соответственно k различным значениям b имеем k классов чисел по модулю k.

Рассмотрим случай k=3. Имеем три класса чисел по модулю 3:

{0 } = {…-9, -6, -3, 0, 3, 6,…}, { 1 } = {-8, -5, -2, 1, 4, 7,…},

{2 } = {…-7, -4, -1, 2, 5, 8,…}.

Любое число класса называется вычетом по модулю k по отношению ко всем числам этого класса. Из свойств сравнений известно, что если x≡a(mod k),

а y≡b(mod k), то x+y≡a+b(mod k), x·y≡a·b(mod k). Тем самым определены опе-

рации сложения и умножения классов вычетов по модулю k : { a }+{ b }={ a+b }, { a }·{ b }={ a·b }.

Взяв от каждого класса по вычету, получим полную систему вычетов.

Чаще всего в качестве представителей классов вычетов берут наименьшие неотрицательные вычеты 0,1, ...,(k-1). Полная система вычетов по модулю простого числа р (k=р) удовлетворяет всем законам поля, и поэтому можно утверждать, что простое поле характеристики р изоморфно (Изоморфизм - соот-

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

веденная выше полная система вычетов по модулю 3 дает простое поле GF(3) =(0, 1, 2 ) характеристики 3.

Пример 2. Представить классы вычетов по модулю чисел 7 и 10. Показать, что полная система вычетов по модулю 7 (7-простое число) является полем, а по модулю 10 - нет (10=5·2 - не является простым числом).

Классы вычетов по модулю простого числа 7:

{0 } = {-14, -7, 0, 7, 14, …}, { 1 } = {-13, -6, 1, 8, 15, …},

{2 } = {-12, -5, 2, 9, 16, …}, { 3 } = {-11, -4, 3, 10, 17, …},

{4 } = {-10, -3, 4, 11, 18, …}, { 5 } = {-9, -2, 5, 12, 19, …},

{6 } = {-8, -1, 6, 13, 20, …}.

Полная система вычетов 0, 1, 2, 3, 4, 5, 6. Проверим, выполняются ли для этого множества законы поля. Среди элементов этого множества имеются элементы 1 и 0 - единичные элементы относительно операций соответственно умножения и сложения. Любая сумма и произведение элементов приводят к элементам того же множества. Приведем некоторые примеры:

81

1 1, 2 2, 3 3, 4 4, 5 5, 6 6 , то есть все элементы, кроме 0, имеют обратные элементы. Все это позволяет назвать полную систему вычетов 0, 1, 2, 3, 4, 5, 6 по модулю 7 полным конечным полем характеристики 7: GF(7)=(0, 1, 2, 3, 4, 5, 6).

Рассмотрим полную систему вычетов по модулю 10:

{0 } = {-20, -10, 0, 10, 20, …}, { 1 } = {-19, -9, 1, 11, 21, …},

{2 } = {-18, -8, 2, 12, 22, …}, { 3 } = {-17, -7, 3, 13, 23, …},

{4 } = {-16, -6, 4, 13, 24, …}, { 5 } = {-15, -5, 5, 15, 25, …},

{6 } = {-14, -4, 6, 16, 26, …}, { 7 } = {-13, -3, 7, 17, 27, …},

{8 } = {-12, -2, 8, 18, 28, …}, { 9 } = {-11, -1, 9, 19, 29, …}.

В качестве представителей классов вычетов возьмем, как и в предыдущем случае, наименьшие положительные значения вычетов 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Это множество элементов уже не будет полем. Хотя в результате сложения и умножения по модулю 10 любых элементов получатся элементы, принадлежащие этому же множеству, обратные элементы по умножению будут иметь не все элементы, отличные от 0. Так, например, элементы 2, 4, 5 не будут иметь обратных элементов, так как ни при каком r не делится (1+10·r) на 2, 4 и 5.

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

Приведем пример расширения GF(23) степени 3 простого поля GF(2). Элементами поля GF(2) будут 0 и 1. Эти элементы будут элементами и поля GF(23). Кроме того, его элементами также будут все возможные полиномы степени не выше 2. Таким образом, поле GF (23) будет содержать элементы: 0, 1, х, 1+х, 1+х+х2, 1+х2, х+х2, х2. Мы задали множество из 23 элементов. Но пока это множество еще не является полем, так как не определены между его элементами операции сложения и умножения. Для этого надо задать полином степени m (в нашем случае m=3), по модулю которого будут проводиться вычисления при сложении и умножении. По аналогии с простым полем Галуа GF(р), элементами которого является полная система вычетов по модулю числа p, элемента-

82

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

Полином Р(x) степени m>1 с коэффициентами из поля GF(p) неприводим над полем GF(р), если он не может быть представлен в виде произведения полиномов меньшей степени над полем GF(р).

Поясним понятие вычетов по модулю какого-то полинома. Сравнение полиномов А (х) и B(x) по модулю Р(x)

эквивалентно равенству А(x)-В(x)=K(x)P(x) для некоторого полинома К(x). Все операции с коэффициентами при x в одинаковых степенях проводятся по модулю р - характеристики простого поля GF(p), элементы которого используются в качестве коэффициентов в полиномах, В(x) - это остаток от деления полинома A(x) на полином Р(x). Все полиномы А(x) над полем GF(р), которые при делении на P(x) дают один и тот же остаток, образуют класс вычетов полиномов по модулю Р(x). Обычно в качестве представителя класса вычетов по модулю полинома берется полином наименьшей степени R(x) , класс вычетов обозначается {R(x)} или R(x) (mod Р(x)).

В соответствии со свойством сравнений, если

A(x)≡R1(x)(mod Р(x)) и B(x)≡R2(x)(mod Р(x)), то A(x)+B(x)≡R1(x)+R2(x)(mod Р(x)) и A(x)·B(x)≡R1(x)·R2(x)(mod Р(x)).

Тем самым определены операции сложения и умножения классов вычетов по модулю полинома P(x):

{R1(x) }+{ R2(x) }={ R1(x)+R2(x) },

{R1(x) }·{ R2(x) }={ R1(x)·R2(x) }.

Если полином Р(x) является неприводимым над полем GF(p), то полная система вычетов по модулю этого полинома образует конечное поле GF(pm), m - степень полинома Р(x).

Для определения поля GF(23) зададим операции сложения и умножения по неприводимому полиному x3+x+1. Кстати, для m=3 существует еще один неприводимый полином x3+x2+1, а два других возможных полиномов 3-ей степени не являются неприводимыми x3+x2+x+1=(x+1)(x2+1), x3+1=(x+1)3, так как они могут быть представлены в виде произведения полиномов меньшей степени.

83

Из таблиц 3.4 и 3.5 видно, что умножение и сложение элементов поля приводит к элементам этого поля, то есть в поле GF(23) заданы операции умножения и сложения. В табл. 3.4 и 3.5 элемент 0 не приводится, так как операции с ним однозначно определены как А(x)+0=А(x) и А(x)·0=0 и не зависят от вида неприводимого полинома.

При смене полинома изменится только таблица умножения. Например, для неприводимого полинома x3+x2+1 умножение элементов GF(23) даст ре-

зультаты: (1+x)·x2=1, (1+x2)·(1+x)=x, (1+x2)·(1+x2)=x2+x. Поясним подробнее

процесс умножения полиномов по модулю какого-то полинома: (1+x+x2)·(x+x2)=x+x2+x3+x2+x3+x4=x+x4. Здесь мы провели сложение по модулю

р=2 коэффициентов при одинаковых степенях x.

Теперь надо определить остаток от деления на неприводимый полином.

Деление проводится как деление обычных многочленов, но вычитание коэффициентов при x в одинаковых степенях должно проводиться по модулю простого числа р. В рассматриваемом случае р=2, при использовании этого модуля операции сложения и вычитания эквивалентны 1+1=0(mod 2), 1-1=0, 0+1=1, 0-1=р-1=2-1=1(mod 2) - в последнем выражении 0 заменяется на р=2, так как р=0(mod p). При определении остатка при делении вычитание заменено суммированием по модулю два. Следовательно,

(1+x+x2)·(x+x2)=x2(mod(x3+x+1))=(1+x2)(mod(x3+x2+1)).

Остаток от деления можно определить и по-другому. Из этого следует, что полином B(x)=A(x)-K(x)·P(x), где А(x) - исходный полином, степень которого выше степени В(x),

Р(x) - полином, по модулю которого вычисляется А(x), К(x) - какой-то полином.

84