2.2. Примитивные элементы
Примитивным элементом поля GF(q) называется такой элемент , что все элементы поля, за исключением 0, могут быть представлены в виде степени элемента . Например, в поле GF(5) = 2, 21=2, 22=4, 23=3, 24=1, так что 2 является примитивным элементом поля GF(5). Примитивные элементы полезны при построении полей, если один из них найден, то, перемножая степени этого примитивного элемента, можно составить таблицу умножения в поле. Каждое поле содержит примитивный элемент.
Пусть 1, 2,…, q-1 ненулевые элементы поля GF(q), тогда
хq-1-1 = (x - 1)(x - 2)…(x - q-1),
и пусть - какой-либо ненулевой элемент из GF(q), тогда
q-1 = ( - 1)( - 2)…( - q-1) = 1
Тогда является корнем многочлена xq-1-1.
Группа ненулевых элементов поля GF(q) по умножению является циклической. Для простого q-1 это тривиально, так как порядок всех элементов, за исключением 0 и 1 равен q-1, так что каждый элемент примитивен. В каждом поле Галуа имеется примитивный элемент [7].
2.2.1 . Структура конечного поля
С помощью примитивного элемента можно построить поле Галуа. Например, в поле GF(8) порядок каждого ненулевого элемента равен 7 или делит на 7, так как 7 – простое число. Поэтому каждый ненулевой элемент является примитивным. Поле GF(8) можно построить с помощью многочлена p(x) = x3+x2+1. Другие неприводимые многочлены приведены в таблице приложения 2. Основываясь на примитивном элементе , который является корнем p(x) получим:
= x1 = 010,
2 = x2 = 100,
3 = x2+1 = 101,
4 = x2+ x+1 = 111,
5 = x+1 = 011,
6 = x2+ x = 110,
7
= 0
=
x0
= 001.
В таком представлении умножение и сложение выполняется легко. Например,
5 6 = 4, 5 + 6 = 3.
При построении расширения поля в виде множества многочленов удоб-но, чтобы примитивному многочлену соответствовал примитивный элемент поля. Тогда построение поля можно осуществлять с помощью простых многочленов, называемых примитивными. Примитивным многочлен p(x) над полем GF(q) называется простой многочлен над GF(q), такой, что в расширении поля, построенным по модулю p(x), соответствующему многочлену, элемент поля является примитивным. Для каждого поля существуют примитивные многочлены всех степеней [7].
Число элементов наименьшего подполя поля GF(q) называется характеристикой поля GF(q). Каждое поле Галуа содержит единственное наименьшее подполе, число элементов которого равно простому числу. Следовательно, характеристика каждого поля Галуа является простым числом. Например, для GF(32) наименьшее подполье GF(2) содержит два элемента.
В поле Галуа GF(q) можно построить подполе GF(p), где p – простое число. В частности, если q является простым числом, то поле GF(q) можно интерпретировать как поле чисел по модулю q. Следовательно, для заданного простого числа существует только одно поле с заданным числом элементов, хотя оно может быть представлено разными способами. Два поля, отличающиеся только представлениями, называются изоморфными.
Пусть GF(q) – некоторое поле, пусть GF(Q) – расширение поля GF(q) и пусть - элемент GF(Q). Простой многочлен f(x) наименьшей степени над GF(q), для которого f() = 0, называется минимальным многочленом элемента над GF(q). Каждый элемент из GF(Q) имеет единственный минимальный многочлен над GF(q). Если минимальный элемент многочлена f(x) равен и является корнем многочлена g(x), то f(x) делит g(x).
Элемент является всегда корнем многочлена xQ - x, который разлагается на простые многочлены над полем GF(q):
хQ – x = f1(x) f2(x)…fk(x).
Если Q
= qm,
то каждый делитель многочлена x
-
x,
неприводимый над полем GF(q),
имеет степень равную m
или меньшую.
При Q = q разложение сводится к равенству:
хq - x = x(x - 1)(x - 2)…(x - q-1).
Следовательно, минимальный многочлен над полем GF(q) элемента , принадлежащего GF(q), является многочленом первой степени f(x) = x - .
Пусть - примитивный элемент поля Галуа GF(Q), являющегося расширением поля GF(q), и пусть m – степень минимального многочлена f(x) элемента над GF(q). Тогда число элементов в поле равно Q = qm и каждый элемент может быть представлен в виде:
= am-1m-1+ am-2m-2+…+a1+a0,
где am-1, am-2, …, a0 – элементы поля GF(q).
В данном случае порядок элемента (или цикл повторения) равен делителю числа qm-1. Например, все ненулевые элементы поля GF(64) могут быть представлены как степени примитивного элемента . Этими элементами являются 0, 1, , 2, …, 62, и
х63 - x = x(x - 1)(x - )(x - 2)…(x - 62).
Так как (21)3 = 63 = 1, то порядок элемента 21 равен 3. Тот же порядок имеет элемент 42.
Каждое поле Галуа содержит pm элементов, где p – некоторое простое число, а m – положительное целое число.
В поле GF(q) = GF(pm) характеристики p для любых элементов , и любого положительного целого m справедливо
Здесь
и
также корни многочлена x
-
x
и множество корней замкнуто относительно
операции сложения.
Для каждого целого положительного m над каждым конечным полем GF(q) существует хотя бы один простой многочлен степени m.
Двойственный многочлен f(x) для f(x) определяется как
xm
f
,
где m – степень f(x).