ПРИМИТИВНЫЕ ЭЛЕМЕНТЫ

В предыдущем параграфе было построено поле GF(4). На рис. 2.2 видно, , за исключением нуля, все элементы поля могут быть представлены в виде степени элемента х.

Определение 24.5.1.Примитивным элементом поля GF(q) называется такой элемент α, что все элементы поля, за исключением нуля, могут быть представлены в виде степени элемента α.

 

 

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

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

 

Теорема 2.5.2.Пусть β₁, β₂, … β_q-1 поля ненулевые элементы поля GF (q); тогда

 

x^q-1 -1 =(x- β₁) (x- β₂ ) …(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,

 

так что β является корнем многочлена (x^q-1 -1)

 

 

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

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

_s

: q-1=∏ p_i^νi

ⁱ⁼¹

Так как GF(q) — поле, то среди его q-1 ненулевых элементов должен найтись хотя бы один, не являющийся корнем мн огочлена

Хx^{(q-1)/ р1i}- -1 1 поскольку этот многочлен может иметь не более (q-1)/рp_ii корней. Следовательно, для каждого i можно найти такой ненулевой элемент а_i поля GF(q), что

 

 

 

 

(qⁱ-1)/p_i^νi _s

 

α_i^{(q-1)/ р1i}≠1. Пусть b_i= а_i, -1 и пусть b = ∏ΠГБ =bi.1&(- Докажем. что порядок Ьb равен q-1

ⁱ⁼¹

= а.

—1 и, следовательно, группа является циклической.

(qi-1)/pi^νi

Шаг 1 Порядок элемента Ьb_iГ равен p_i^ύ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 Ъ^ ^-. Но b_i =a_i ≠1

«р/ =-- а^~ ' т^= 1 , и, следовательно, порядок элемента bi равен pi^ύi.

Ч 1)_Г равен /?* .

Шаг 2. Порядок элемента bЬ равен qд — 1. Доказательство. Предположим, что bⁿЬ^п = 1. Покажем сначала, что из этого следует равенство п ---= 0 (mod pi^ύi той р_г^г) для всех iI = 1, ..., sз. Для каждого iI можно записать

 

(n ∏ pi^ύi)

b ^j≠i =1

_{s pi}^ύj ( n ∏ pj^ύj )

ибо, зЗаменяя bЬ на ∏ bⁱЦ? =1^1 ^и и используя равенство b_jЬр' = 1, находим b ^j≠i

ⁱ⁼¹

Поскольку рг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)=z³ + z + 1 . Основываясь на примитивном элементе ά. = z, имеем

 

 

ά= z(mod p(z)) = z;

ά²= z²(mod p(z))= z²

ά³= z³(mod p(z) =z + 1);

 

ά⁴ = z² + z(mod p(z))= z² +z

 

ά⁵= z³ + z²(mod p(z))=z² + z + 1

 

ά⁶= z³ + z² + z(mod p(z))=z² +1;

 

ά⁷= z³ + z(mod p(z))=1

В таком представлении умножение выполняется легко; например, ά⁴ * ά⁵= ά⁷* ά²= ά².

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

ά= z(mod p(z)) = z;

ά²= z²(mod p(z))= z²

ά³= z³(mod p(z) =z³;

 

ά⁴ = z⁴(mod p(z))= z+1

 

ά⁵= z² + z (mod p(z))= z² + z

 

ά⁶= z³ + z²(mod p(z))= z³ + z²;

 

ά⁷= z⁴ +z³(mod p(z)) = z³+ z+1;

ά⁸= z² +z² +z(mod p(z))= z² +1

ά⁹= z³ +z(mod p(z) =z³ +z;

 

ά¹⁰ = z⁴ + z²(mod p(z))= z² +z+1

 

ά¹¹= z³ + z² +1(mod p(z))=z³ + z² + z

 

ά¹²= z⁴ + z³ + z²(mod p(z))= z³ + z²+z +1;

 

ά¹³= z⁴ + z³ + z²+ z(mod p(z))= z³ + z²⁺1

ά¹⁴ = z⁴ + z³+z(mod p(z))= z³ +1

ά¹⁵ =z⁴ + z(mod p(z))=1

В таком представлении поля умножение опять просто; например,

ά ¹¹- ά ¹³ = ά ¹⁵- ά ⁹ = ά⁹.

При построении расширения поля в виде множества многочленов удобно, чтобы многочлену х соответствовал примитивный элемент поля. В этом случае в таблице умножения можно использовать х в качестве основания логарифмов, и это самое простое из возможных оснований. Такое построение поля можно осуществить с помощью простых многочленов специального частного вида, называемых примитивными.

Определение 2.5.5. Примитивным многочленом р (х) над по­лем GF(q) называется простой многочлен над GF(q), такой, что в расширении поля, построенном по модулю р (х), соответствующий многочлену х элемент поля является примитивным.

 

Для каждого поля Галуа существуют примитивные многочлены всех степеней, но доказательство этого результата мы откладываем до конца следующего параграфа. Предваряя этот результат, можно сказать, что примитивный многочлен представляет соой простой многочлен, корнем которого является примитивный элемент поля.