В предыдущем параграфе было построено поле GF(4). На рис. 2.2 видно, , за исключением нуля, все элементы поля могут быть представлены в виде степени элемента х.
Определение 24.5.1.Примитивным элементом поля GF(q) называется такой элемент α, что все элементы поля, за исключением нуля, могут быть представлены в виде степени элемента α.
Например, в поле GF(5) 21 =- 2, 22 = 4, 23 = 3, 24 = 1, так что 2 является примитивным элементом поля GF(5). Примитивные элементы полезны при построении полей, так как если один из них найден, то, перемножая степени этого примитивного элемента, можно построить таблицу умножения в поле. В данном параграфе будет доказано, что каждое поле содержит примитивный элемент.
Поле образует абелеву группу двояким способом. Множество всех элементов поля образует абелеву группу по сложению, и множество всех элементов поля, исключая нуль, образует абелеву группу по умножению. Мы будем работать с группой по умножению. Согласно теореме 1.2.5, порядок этой группы делится на порядок каждого ее элемента
Теорема 2.5.2.Пусть β1, β2, … βq-1 поля ненулевые элементы поля GF (q); тогда
xq-1 -1 =(x- β1) (x- β2 ) …(x- βq-1)
Доказательство.Множество ненулевых элементов поля GF(q) образует конечную группу по умножению. Пусть β, — какой-либо ненулевой элемент из GF(q), и пусть h — порядок этого элемента по умножению. Тогда, согласно теореме 1.2.5, h делит q — 1. Следовательно,
β q-1= (βh)(q-1)/h=(1)(q-1)/h=1,
так что β является корнем многочлена (xq-1 -1)
Теорема 2.5.3.Группа ненулевых элементов поля GF(q) по умножению является циклической.
Доказательство.Если число q- 1 простое, то теорема тривиальна, ибо порядок всех элементов, за исключением нуля и единицы, равен q-1, так что каждый такой элемент примитивен. Доказывать теорему надо только для составного числа q-1 . Рассмотрим разложение числа q-1 на простые множители
s
: q-1=∏ piνi
i=1
Так как GF(q) — поле, то среди его q-1 ненулевых элементов должен найтись хотя бы один, не являющийся корнем мн огочлена
Хx(q-1)/ р1i- -1 1 поскольку этот многочлен может иметь не более (q-1)/рpii корней. Следовательно, для каждого i можно найти такой ненулевой элемент аi поля GF(q), что
(qi-1)/piνi s
αi(q-1)/ р1i≠1. Пусть bi= аi, -1 и пусть b = ∏ΠГБ =bi.1&(- Докажем. что порядок Ьb равен q-1
i=1
= а.
—1 и, следовательно, группа является циклической.
(qi-1)/piνi
Шаг 1 Порядок элемента ЬbiГ равен piύi/?;г. Доказательство.
piύi ύi ni
*Г
Очевидно, что Ь ^ bi = 1, так что порядок элемента biЬ1 делит piрЛ. Он равен числу вида pi/;"*. Если niи.
pi ύi-1 pi ύvi-1 (q-1)/pi
меньше ύiύIv,-, то bi = 1 Ъ^ ^-. Но bi =ai ≠1
«р/ =-- а^~ ' т^= 1 , и, следовательно, порядок элемента bi равен piύi.
Ч 1)Г равен /?* .
Шаг 2. Порядок элемента bЬ равен qд — 1. Доказательство. Предположим, что bnЬп = 1. Покажем сначала, что из этого следует равенство п ---= 0 (mod piύi той ргг) для всех iI = 1, ..., sз. Для каждого iI можно записать
(n ∏ piύi)
b j≠i =1
s piύj ( n ∏ pjύj )
ибо, зЗаменяя bЬ на ∏ biЦ? =1^1 и и используя равенство bjЬр' = 1, находим b j≠i
i=1
Поскольку ргpi являются различными простыми числами, то п = ~ 0 (mod piύiтос! рТ*) для каждого iI. Следовательно, п = q-1.П;=1р1г<
Теорема доказана. П
Эта теорема дает важнейший ключ к пониманию структуры
полей Галуа, а именно следующее утверждение.
Теорема 24.5.4.В каждом поле Галуа имеется примитивный элемент.
Доказательство.Так как ненулевые элементы поля GFСР (qд)
образуют циклическую группу, то среди них имеется элемент
порядка д=q—1. Этот элемент является примитивным. П
Использование примитивного элемента для умножения в поле иллюстрируется следующими примерами.
В поле GFСР (88) порядок каждого ненулевого элемента делит 7. Так.
ак как 7 — простое число, то каждый элемеент, за исключением
нуля и единицы, имеет порядок, равный 7, и, следовательно ,
примитивен., Поле GFСР (8) можно построить с помощью многочлена
p(z)=z3 + z + 1 . Основываясь на примитивном элементе ά. = z, имеем
ά= z(mod p(z)) = z;
ά2= z2(mod p(z))= z2
ά3= z3(mod p(z) =z + 1);
ά4 = z2 + z(mod p(z))= z2 +z
ά5= z3 + z2(mod p(z))=z2 + z + 1
ά6= z3 + z2 + z(mod p(z))=z2 +1;
ά7= z3 + z(mod p(z))=1
В таком представлении умножение выполняется легко; например, ά4 * ά5= ά7* ά2= ά2.
Порядок каждого элемента в поле GF(16) делит 15. Элемент может иметь порядок 1, 3, 5 или 15. Поле GF(16) можно построить с помощью многочлена р (z) = z4 + z + 1 и примитивного элемента ά = z; имеем
ά= z(mod p(z)) = z;
ά2= z2(mod p(z))= z2
ά3= z3(mod p(z) =z3;
ά4 = z4(mod p(z))= z+1
ά5= z2 + z (mod p(z))= z2 + z
ά6= z3 + z2(mod p(z))= z3 + z2;
ά7= z4 +z3(mod p(z)) = z3+ z+1;
ά8= z2 +z2 +z(mod p(z))= z2 +1
ά9= z3 +z(mod p(z) =z3 +z;
ά10 = z4 + z2(mod p(z))= z2 +z+1
ά11= z3 + z2 +1(mod p(z))=z3 + z2 + z
ά12= z4 + z3 + z2(mod p(z))= z3 + z2+z +1;
ά13= z4 + z3 + z2+ z(mod p(z))= z3 + z2+1
ά14 = z4 + z3+z(mod p(z))= z3 +1
ά15 =z4 + z(mod p(z))=1
В таком представлении поля умножение опять просто; например,
ά 11- ά 13 = ά 15- ά 9 = ά9.
При построении расширения поля в виде множества многочленов удобно, чтобы многочлену х соответствовал примитивный элемент поля. В этом случае в таблице умножения можно использовать х в качестве основания логарифмов, и это самое простое из возможных оснований. Такое построение поля можно осуществить с помощью простых многочленов специального частного вида, называемых примитивными.
Определение 2.5.5. Примитивным многочленом р (х) над полем GF(q) называется простой многочлен над GF(q), такой, что в расширении поля, построенном по модулю р (х), соответствующий многочлену х элемент поля является примитивным.
Для каждого поля Галуа существуют примитивные многочлены всех степеней, но доказательство этого результата мы откладываем до конца следующего параграфа. Предваряя этот результат, можно сказать, что примитивный многочлен представляет соой простой многочлен, корнем которого является примитивный элемент поля.