2. Порождение элементов поля gf(pn)1) .

Итак, конечные поля порядка pⁿ, где характеристика p  простое число, а размерность n  натуральное число, порождаются с помощью неприводимых многочленов степени n. В особенности удобно использовать примитивные неприводимые многочлены ; в этом случае соответственно изложенному выше простое поле GF(p) может быть расширено до поля за счет присоединения к полю GF(p) корня многочлена (при этом приходим к операциям в расширенном поле по двум модулям p и ).

Алгоритм последовательного образования элементов расширенного поля GF(pⁿ) сводится к следующему:

1. корень многочлена выбирается как примитивный элемент поля, то есть принимается = 0, откуда вытекает , где  многочлен -ой степени, полученный из равенства = 0 переносом старшего терма в левую сторону.

2. элементы поля сопоставляются со степенями и двоичными комбинациями из n компонент:

N = 0 (000...000) 

N = 1 (000...001)

N = 2 (000...010)

. . . . . . . . .

N = n  1 (010...000)

N = n (100...000)

3. элементы поля получаются один за одним путем сдвига влево предыдущей комбинации для всех n разрядов, при этом, если в -м разряде слева (разряде переполнения) оказывается 0, то полученная в результате сдвига комбинация остается без изменения; в другом случае, если в указанном разряде переполнения появляется 1, то она откидывается, а к полученной комбинации прибавляется поразрядно по модулю 2 двоичное представление .

Комментарий. Таким образом, примитивным элементом берется комбинация (000...010), то есть N = 2. Двоичные комбинации для N, которые равняются , содержат строго по одной единице, которая последовательно сдвигается влево  в сторону старших разрядов, что отвечает умножению предыдущего элемента N на . Дальнейший сдвиг влево для получения элемента N = , то есть , приводит к переполнению  возникновению -го разряда. Это переполнение устраняется с помощью коррекции путем прибавления к разрядам по модулю 2 двоичного представления , которое равняется (по модулю неприводимого многочлена ) значению разряда переполнения . Процесс формирования элементов полей для n = 2, ..., 5 иллюстрируют табл.1,2.

Если характеристика поля , то процедура генерации элементов отличается лишь тем, что в разряде переполнения может появиться любой элемент

Таблица 1. Порождение полей Галуа характеристики 2 маленьких порядков.

,		, ,				, ,
N	GF	N	GF	N	GF	N	GF	N	GF
0	0 0	0	0 0 0	4	0 1 1	0	0 0 0	4	1 0 1
1	0 1	1	0 0 1	5	1 1 0	1	0 0 1	5	1 1 1
2	1 0	2	0 1 0	6	1 1 1	2	0 1 0	6	0 1 1
3	1 1	3	1 0 0	7	1 0 1	3	1 0 0	7	0 1 0

Таблица 2. Порождения полей Галуа характеристики 2 маленьких порядков

,		,
N	GF	N	GF	N	GF
0	0 0 0 0	0	0 0 0 0 0	16	1 1 1 1 1
1	0 0 0 1	1	0 0 0 0 1	17	1 1 0 1 1
2	0 0 1 0	2	0 0 0 1 0	18	1 0 0 1 1
3	0 1 0 0	3	0 0 1 0 0	19	0 0 0 1 1
4	1 0 0 0	4	0 1 0 0 0	20	0 0 1 1 0
5	0 0 1 1	5	1 0 0 0 0	21	0 1 1 0 0
6	0 1 1 0	6	0 0 1 0 1	22	1 1 0 0 0
7	1 1 0 0	7	0 1 0 1 0	23	1 0 1 0 1
8	1 0 1 1	8	1 0 1 0 0	24	0 1 1 1 1
9	0 1 0 1	9	0 1 1 0 1	25	1 1 1 1 0
10	1 0 1 0	10	1 1 0 1 0	26	1 1 0 0 1
11	0 1 1 1	11	1 0 0 0 1	27	1 0 1 1 1
12	1 1 1 0	12	0 0 1 1 1	28	0 1 0 1 1
13	1 1 1 1	13	0 1 1 1 0	29	1 0 1 1 0
14	1 1 0 1	14	1 1 1 0 0	30	0 1 0 0 1
15	1 0 0 1	15	1 1 1 0 1	31	1 0 0 1 0

Процесс формирования полей для n = 2 и 3 представлен в табл.3

из ПСЛ по модулю p. В этом случае к текущей n-разрядной комбинации прибавляется по модулю p исправление в виде двоичного представления многочлена , которое домножается на число , удовлетворяющее условию , где умножение также выполняется по модулю p.

Рассмотрим еще один важный для дальнейшего вопрос, связанный с отображениями полей в себя.

Таблица 3. Порождения полей для n = 2,3.

,		, ,
N	GF	N	GF	N	GF	N	GF
0	0 0	0	0 0 0	9	2 0 2	18	2 1 0
1	0 1	1	0 0 1	10	0 1 1	19	1 2 1
2	1 0	2	0 1 0	11	1 1 0	20	2 2 2
3	2 1	3	1 0 0	12	1 1 2	21	2 1 1
4	2 2	4	0 1 2	13	1 0 2	22	1 0 1
5	0 2	5	1 2 0	14	0 0 2	23	0 2 2
6	2 0	6	2 1 2	15	0 2 0	24	2 2 0
7	1 2	7	1 1 1	16	2 0 0	25	2 2 1
8	1 1	8	1 2 2	17	0 2 1	26	2 0 1