Предположим теперь, что мы хотим построить порождающий многочлен g (х), имеющий своими корнями элементы Pi, р. Обозначим через Д (х), .... (х) минимальные многочлены этих элементов. Тогда

g{x) НОК [/i(x), f,{x), /Лл-)1,

и таким образом задача сводится к отысканию минимального многочлена f (х) заданного элемента р.

Пусть степень минимального многочлена f (х) элемента р равна т. Тогда в GF (9") он должен иметь т корней. Эти дополнительные корни можно описать следующими двумя теоремами.

Теорема 5.3.3. Пусть характеристика поля GF (q) равна р. Тогда для любого многочлена s [х) над GF (q) и произвольного целого т выполняется равенство

= Ц sfxv"

это равенстве справедливо также при замене р любой его степенью.

Доказательство. Начнем с /?г = 1 и будем рассуждать так же, как при доказательстве теоремы 4.6.10. Чтобы сократить число шагов, определим многочлен s (х) равенством s (х) == s (х) х -i- s; тогда

(P\ Pl P(P-1)! \iJ n{p~i)\ t!(p-t)!

И p является простым числом, которое не входит в знаменатель, за исключением случаев i = О и i = р, так что () представляет собой целое число, кратное р, т. е. равное нулю по модулю р. Следовательно,

[six)]p = [s ix)VxP + sP.

Применим теперь те же рассуждения к многочлену s (х) и продолжим вычисления. Это даст доказательство утверждения для m = 1:

[s(x)] = Ssfx".

Далее,

«=о

Ц six" L t=o

= S sfx"".

Эти вычисления можно повторить произвольное число раз, так что теорема верна при замене р любой его степенью. □

Теорема 5.3.4. Предположим, что f {х) над GF (д) является минимальным многочленом элементп [3 из GF (д"). Тогда f (х) является также минимальным многочленом элемента Р.

Доказательство. Так как д равно степени характеристики р поля, то теорема 5.3.3 дает

deg f (Х-)

Ho коэффициенты /j принадлежат полю GF (g), a все элементы этого поля удовлетворяют условию у = у. Следовательно,

deg f (X)

1ПФ= fi{.xYf{x%

и так как / (Р) = О, то О = [/ (Р) ]" = / (Р), и, следовательно, р является корнем многочлена / {х). Поскольку / (х) - простой многочлен, он является минимальным многочленом элемента Р, и теорема доказана. □

Определение 5.3.5. Два элемента из поля GF {д"), являющиеся корнями одного и того же минимального многочлена над GF (д), называются сопряженными (относительно поля GF (д)).

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

Два элемента из GF (16) могут быть сопряжены относительно поля GF (2) и не сопряжены относительно поля GF (4).

Используя теорему 5.3.4, легко выписать все сопряженные с р элементы. Если многочлен / (х) является минимальным для элемента Р, то он минимален и для элемента р, и для р и т. д. Следовательно, сопряжены все элементы множества

{р, р f", p"l.

где г - наименьшее целое число, такое, что Р" = р. Заметим,

что так как Р" = Р, то г < /п. Выписанное выше множество называется множеством сопряженных элементов. Все сопряженные элементы являются корнями многочлена f {х), и следующая теорема показывает, что других корней нет,

Теорема 5.3.6. Минимальный многочлен элемента р равен

/(х):(х-р)(х-р)...(х- f). Доказательство. Согласно теореме 5.3.4, все эти элементы действительно должны быть корнями минимального многочлена

элемента р, так что степень минимального многочлена не может быть меньше. Поэтому нам надо только показать, что все коэффициенты f (х) принадлежат полю GF (q). Воспользуемся тем фактом, что все корни многочлена хч - х образуют подполе поля GF (q"). Прежде всего вычислим [/(х) ]«:

[/ (л:)] == (л: - Р) (х - р)-? . . . {х - f/)" = = (х-р*)(х«-р). . . (х-Р), где второе равенство вытекает из теоремы 5.3.3 и того факта, что р = р. Таким образом,

в то время как теорема 5.3.3 утверждает, что

.1 j i

Следовательнр, Я = ft Для каждого i, и Д- принадлежит подполю GF (q), что и требовалось доказать. □

Например, выберем а равным примитивному элементу поля GF (256). Тогда множество

{а, a а*. а\ а, а«*, а»)

представляет собой множество сопряженных элементов. Оно заканчивается элементом а, так как = 1, и, следовательно, абб 0 - элементу, уже содержащемуся в множестве. Минимальный многочлен элемента а равен многочлену

f (х) = {х - а){х - а) (х - а*) ... (х - а"*) (х - ai),

все коэффициенты которого (после раскрытия скобок) будут элементами поля GF (2). Аналогично множеством сопряженных элементов, содержащих элемент а, будет

{a ai*, а", а?, а>, a}],

а минимальный многочлен элемента равен

f (х) = (х - а) (X - а*) (х - а) ... (х - а!») ( ai8i)

все коэффициенты которого (после раскрытия скобок) будут элементами поля GF (2).

Теперь вместо GF (2) выберем в качестве основного поля GF (4), которое также является подполем поля GF (256); тогда множеством сопряженных элементов, содержащим и, будет

я минимальный многочлен элемента над полем GF (4) равен

/ (Х) = (X - а) - «28) (J, a"2) „193)