Например, в поле GF (5) 2 = 2, 2 = 4, 2 = 3, 2* = 1, так что 2 является примитивным элементом поля GF (5). Примитивные элементы полезны при построении полей, так как если один из них найден, то, перемножая степени этого примитивного элемента, можно построить таблицу умножения в поле. В данном параграфе будет доказано, что каждое поле содержит примитивный элемент.

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

Теорема 4.5.2. Пусть Pi, р., P i-ненулевые элементы поля GF (q); тогда

х- 1 = (X - Pi) (х - р,) .. . (х - p, i).

Доказательство. Множество ненулевых элементов поля GF {q) образует конечную группу по умножению. Пусть Р - какой-либо ненулевой элемент из GF (q), и пусть h -порядок этого элемента по умножению. Тогда, согласно теореме 2.2.5, h делит q-I. Следовательно,

Р?-! = (pft)(?-i)/ft = ito-D/ft = 1,

так что р является корнем многочлена х- -1. □

Теорема 4.5.3. Группа ненулевых элементов поля GF (q) по умножению является циклической.

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

Так как GF (q) - поле, то среди его q-1 ненулевых элементов должен найтись хотя бы один, не являющийся корнем многочлена i4-i)/Pi -поскольку этот многочлен может иметь не более {q~-\)ipi корней. Следовательно, для каждого г можно найти такой ненулевой элемент С{ поля GF {q), что а\ Ф 1. Пусть &j =

= af~"i, и пусть b - n?=ibi- Докажем,что порядок b равен q-1 и, следовательно, группа является циклической.

Ь\ / = 1.

Заменяя b на Xlf=it и используя равенство b.i = 1, находим

ь \ /= / = 1.

Таким образом.

«npp=0(modpp).

Поскольку Pi являются различными простыми числами, то п = = О (mod р1) для каждого г. Следовательно, п = Hjyt?]*. Теорема доказана. □

Эта теорема дает важнейший ключ к пониманию структуры полей Галуа, а именно следующее утверждение.

Теорема 4.5.4. В каждом поле Галуа имеется примитивный элемент.

Доказательство. Так как ненулевые элементы поля GF (q) образуют циклическую группу, то среди них имеется элемент порядка q-l. Этот элемент является примитивным. □

Использование примитивного элемента для умножения в поле иллюстрируется следующими примерами.

В поле GF (8) порядок каждого ненулевого элемента делит 7. Так как 7 - простое число, то каждый элемен!, за исключением нуля и единицы, имеет порядок, равный 7, и, следовательно, примитивен Поле GF (8) можно построить с помощью многочлена

Шаг 1. Порядок элемента bi равен pi\ Доказательство. Очевидно, что b. =1, так что порядок элемента Ь. делит pp. Он равен числу вида р".к Если п. меньше v,., то fc 1. Но

V.-1

Ь: = с"" Фи и, следовательно, порядок элемента bi равен р]\

Шаг 2. Порядок элемента b равен q-1. Доказательство. Предположим, что Ь" 1. Покажем сначала, что из этого следует

равенство л = о(шсс1 р]) для всех г = 1, s. Для каждого / можно записать

В таком представлении полй умножение Шйп, просто; например.

При Еостроении расширения поля в виде множества многочленов удобно» чтобы многочлену х соответствовал примитивный

р (г) = + г + 1. Основываясь на примитивном элементе а = z, имеем

а = г,

а? = г,

а? = г+1,

«4 = 2 + Z,

«5 = + г + 1,

а" = +1,

а = 1 = аО.

В таком представлении умножение выполняется легко; например, а-а} = а-а? = а?.

Порядок каждого элемента в поле GF (16) делит 15. Элемент может и.меть порядок 1, 3, 5 или 15. Поле GF (16) можно построить с помощью многочлена р {z) = + z + \ и примитивного элемента а = г; имеем