Лекции по дискретной математике, страница 7

ⁱ⁼¹

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

Шаг 1 Порядок элемента b_i равен p_i^ύi. Доказательство.

pi^ύi _{ύi ni}

Очевидно, что bi = 1, так что порядок элемента bi делит pi. Он равен числу вида pi. Если ni

_{ύi-1 ύi-1}

pi pi _(q-1)/pi

меньше ύI,-, то bi=1. Но bi =a_i(q-1)/pi ≠1 и, следовательно, порядок элемента bi равен pi^ύi .

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

(n ∏ pi^ύi)

b ^{j≠I =}1

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

ибо, заменяя b на ∏ bⁱ и используя равенство _bj^pj = 1, находим b ^j≠1

ⁱ⁼¹

Поскольку pi являются различными простыми числами, то п = 0 (mod pi^ύi) для каждого i. Следовательно, п = q-1.

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

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

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

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

В поле GF(8) порядок каждого ненулевого элемента делит 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), такой, что в расширении поля, построенном по модулю р (х), соответствующий многочлену х элемент поля является примитивным.

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

2.6. СТРУКТУРА КОНЕЧНОГО ПОЛЯ

Ранее в данной главе мы изучали, как строить поле. Предполагая, что можно найти простой многочлен степени п над полем ά (q), мы научились строить конечное поле с q^п элементами.

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

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

Определение 2.6.1. Число элементов наименьшего подполя поля GF(q) называется характеристикой поля GF(q).

Теорема 2.6.2. Каждое поле Галуа содержит единственное наименьшее подполе, число элементов которого равно простому числу. Следовательно, характеристика каждого поля Галуа является простым числом.

Доказательство. Поле содержит элементы 0 и 1. Для задания подполя рассмотрим подмножество G = {О, 1, 1 + 1, 1 + 1 + 1, ), обозначая его элементы через {О, 1, 2, 3, ...}. Это подмножество является циклической группой по сложению, которая должна содержать конечное число р элементов. Мы покажем, что р — простое число и что G = GF (р). Сложение в G, является сложением по модулю р, так как G образует циклическую группу по сложению. В силу закона дистрибутивности умножение также должно быть умножением по модулю р, ибо

ά∙р = (1 + ••• + 1)∙р = р +....+ р,

где элемент p суммируется ά раз и суммирование ведется по мо­дулю р. Следовательно, умножение также является умножением по модулю р. По умножению каждый элемент обратим, так как последовательность {p, p², p³, …} образует циклическую подгруппу в G.

Таким образом, подмножество G содержит единичный элемент, замкнуто относительно операций сложения и умножения и содержит элементы, обратные его элементам и по сложению, и по умножению. Следовательно, оно является подполем, и арифметика в этом подполе есть арифметика по модулю р. Но это в точности поле, описываемое теоремой 2.2.3, и, следовательно, р должно быть простым.

В поле Галуа GF(q) мы построили подполе GF (р), где р — простое число. В частности, если q, с которого мы начинаем, само является простым числом, то, как мы видим, поле GF(q) можно интерпретировать как поле чисел по модулю q. Следовательно, для заданного простого числа действительно существует только одно поле с данным числом элементов, хотя, конечно, оно может быть представлено многими разными способами. Два поля, различающиеся только представлениями, называются изоморфными.

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

Определение 2.6.3. Пусть GF(q) —некоторое поле, пусть GF(Q) —расширение поля GF(q), и пусть β —элемент GF(Q). Простой многочлен f(x) наименьшей степени над GF(q), для которого f(β)= 0, называется минимальным многочленом элемента β над GF(q).

Мы должны доказать, что минимальный многочлен всегда существует и является единственным.

Теорема 2.6.4. Каждый элемент β из GF(Q) имеет единственный минимальный многочлен над GF(q). Если минимальный многочлен элемента β равен f(х) и β является корнем многочлена g (х), то f(х) делит g (х).

Доказательство. Прежде всего β всегда является корнем многочлена x^Q-х, представляющего собой многочлен над GF(q). Воспользуемся теоремой об однозначном разложении:

x^Q-х=f₁(x)∙f₂(x)∙….∙f_k(x)

множители в правой части - все простые многочлены над полем GF(q)- Если β —корень левой части, то в правой части должен найтись некоторый член, корнем которого является β. Это может быть только один из членов правой части, так как над расширением GF(Q) простые многочлены дальше разлагаются в произведение линейных членов и констант, и β может быть корнем только одного из линейных членов.

Чтобы доказать вторую часть теоремы, положим

g(x)= f(x) h(x) +s(x),

где степень многочлена s(х) меньше степени f(x;), так что β не может быть его корнем. Но

О =g(β) =f(β) h(β) +s(β); следовательно, s(х) должен равняться нулю, и теорема доказана.

Следствие 2.6.5. Если f₁(x), ∙f₂(x),∙….∙f_k(x) —все различные многочлены над GF(q), являющиеся минимальными для одного или нескольких элементов из GF(Q), то

x^Q-х=f₁(x)∙f₂(x)∙….∙f_k(x)

.

Доказательство следует из теоремы, так как каждый такой элемент β является корнем многочлена х x^Q-х.

При Q = q разложение сводится к равенству

x^q –x =x .(x-β₁)((x-β₂) …(x-β_q-1),