5.3. Поля, основанные

на кольцах многочленов

Поля можно строить, отталкиваясь от колец многочленов, таким же образом, как бы.чи построены конечные ноля из кольца целых чисел. Такая конструкция приводит как к конечным, так и к бесконечным полям в зависимости от того, было ли исходное кольцо многочленов определено над конечным или бесконечным полем. Эти расширения оказались полезными в нескольких направлениях дискретной обработки сигналов. Они были использованы для построения теоретике-числовых преобразований, рассматриваемых в гл. 6, и для построения алгоритмов многомерной свертки, рассматриваемых в гл. 7.

Пусть имеется кольцо многочленов F [х 1 над полем F. Так же как для кольца 2 были построены кольца вычетов, можно построить и для кольца F [х] его факторкольцо. Выбирая из F [х] произвольный многочлен р (х), можно определить такое кольцо, используя р (х) в качестве модуля для задания арифметики этого кольца. Мы ограничим рассмотрение только приведенными много-членами, так как это ограничение снимает ненужную неопреде-ленность построения.

Определение 5.3.1. Для произвольного приведенного многочлена р (х) ненулевой степени над полем F кольцом многочленов по модулю р (х) называется множество всех многочленов над F, степень которых не превосходит степени многочлена р (х), с операциями сложения и умножения многочленов по модулю р (х). Это кольцо принято обозначать через F [х1/(р (х)).

Произвольный многочлен г (х) из F 1х 1 можно отобразить в F [х1/(р(х)), отображая г (х) в Rp(x) Ir (х)]. Два сравнимых по модулю р (х) элемента а (х) и Ь (х) из F (х) отображаются в один и тот же многочлен из F 1х1/(р (х)).

Теорема 5.3.2. Кольцо многочленов по модулю р (х) является кольцом.

Доказательство. Доказательство проводится прямой провер- .J кой выполнения свойств кольца. □

В качестве примера рассмотрим кольцо многочленов над GF (2), выбирая модуль равным р (х) = х + 1. Тогда кольцо многочленов Ш по модулю р (х) равно GF (2) [х1/(г -f 1). Оно состоит из эле-ментов 10, 1, X, X + 1, х; х + \, х + х, х + х + 1,} и умно. , жение в этом кольце выполняется, например, следующим образом:

(X + 1){х) = 1(х + 1) хЦ = [х(х= + 1) + .v= + х1 = = х + X,

где использована редукция по правилу х* = х (х + 1) + х.

В качестве другого примера рассмотрим кольцо многочленов над полем рациональных чисел Q, выбирая р (х) = л + 1, Тогда кольцо многочленов по модулю р (х) есть Q х1/(х=+ 1). Оно содержит многочлены вида а + хЬ. где а и b - рациональные числа. Умножение выполняется по правилу

(а -f xb) (с + xd) = {ас ~ bd) + х (ad + be).

Умножение имеет ту же структуру, что и комплексное умножение; на самом деле рассматриваемое кольцо является полем. Это вытекает из следующей общей теоремы.

Теорема 5.3.3. Кольцо многочленов по модулю приведенного .шогочлена р (х) является полем тогда и только тогда, когда многочлен р (х) прост

Доказательство. Пусть многочлен р (х) прост. Чтобы доказать, что рассматриваемое кольцо образует поле, достаточно показать что каждый ненулевой элемент имеет мультипликативный обратный. Пусть S (х) - некоторый ненулевой элемент кольца. Тогда deg S (х) < deg р (х). Так как многочлен р (х) прост, то НОД (s(x), р(х)1 = I. Согласно следствию 2.7.7,

1 = а (X) р (X) + 6 (X) S (х)

для некоторых многочленов а (х) и Ь (х). Следовательно,

1 = Р( )11] = Rf (x,[a(x)p(x) + b{x)s{x)]

= U) [b(x)]. р [s (x)l = R, ,ц lf> (x)l s (.V).

Таким образом, в кольце многочленов по модулю многочлена р (х) многочлен Rp [b (х) ] является мультипликативным обратным к S (х).

Теперь предположим,., что многочлен р (х) не прост. Тогда-р (х) = г (х) S (х) для некоторых г (х) и s (х). Если кольцо является полем, то многочлен г (х) имеет обратный r~ (х), и поэтому

S (х) = м [S (х)] = [r- (х) г (х) S (х)] =

= р W 1/-(х)-р(х)] = 0.

Но S (х) # О, и мы получаем противоречие. Следовательно, такое кольцо не может быть полем. □

Теорема описывает один из способов построения поля комплексных чисел С как расширения поля вещественных чисел R. Так как многочлен х + 1 является простым над полем вещественных

) Напомним что простой многочлен является одновременно приведенным и неприводимым. Для построения поля достаточно только неприводимости р {х), 110 мы условились рассматривать только приведенные многочлены, так что дальнейшие результаты носят менее общий характер.

5.4. Минимальные многочлены и сопряжения

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

Определение 5.4.1. Пусть F - некоторое поле, а элемент Р принадлежит некоторому расширению поля F. Минимальным многочленом f (х) элемента р над полем F называется ненулевой приведенный многочлен наименьшей степени, такой что коэффициенты его принадлежат основному полю F, а элемент р является корнем.

Минимальный многочлен над полем F существует не для всякого элемента расширения - элементы вещественного поля, не имеющие минимальных многочленов с рациональными коэффициентами, называются трансцендентными числами - но если для данного элемевта минимальный многочлен существует, то он единственен. Действительно, если /ш (х) и Р> (х) оба являются минимальными многочленами элемента р, то они оба приведенные, имеют одну и ту же степень и р является их корнем. Тогда многочлен / (х) = /14 (х) - /<2> (х) имеет меньшую степень и р является его корнем. Следовательно, / (х) = О и /I (х) равен

(х).

Теорема 5.4.2. Каждый минимальный многочлен является единственным и простым. Если f (х) - минимальный многочлен э.кменпш Р, а g (х) - некоторый многочлен, для которого р является корнем, то f (х) делит g (х).

Доказательство. Единственность минимального многочлена мы уже доказали. По определению многочлен f (х) является приведенным. Предположим, что / (х) разлагается в произведение двух многочленов, f (х) = а (х) b (х). Тогда / (Р) = (Р) Ь (Р) = О, так что хотя бы один из многочленов а (х) и b (х) имеет степень, меньшую чем степень f (х), и элемент р служит его корнем. Следовательно, минимальный многочлен является простым.

Для доказательства второй части теоремы запишем

g(x) = f (X) л (X) -Ь S (х).

Степень многочлена s (х) меньше степени / (х), так что s (х) не может иметь элемент р своим корнем. Но

О = g (Р) = / (Р) Л (Р) + S (Р) = S (Р), так что многочлен s (х) равен нулю, и теорема доказана. □

Каждый элемент р поля F имеет над F минимальный многочлен первой степени, равный f (х) = х - . Если элемент р не принадлежит полю F, то степень его минимального многочлена равна двум или больше. Следовательно, минимальный многочлен может иметь и другие корни. Но тогда минимальный многочлен элемента р является минимальным многочленом и для других, отличных от р, элементов.

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

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

чисел, то R МОЖНО расширить до множества 1а + Ьх\, где й и b вещественны, задавая сложение и умножение по модулю х+\. Тогда

(а + Ьх) (с + dx) = (ac - bd) + {ad + be) x, {a + bx) + {c + dx) = {a + c) + {b + d) x. Эти формулы будут более привычны, если вместо х поставить /: {а + jb) + {с+ jd) = {а + с) + j (b + d), {а + jb) (с + id) = (ас - bd) + ; (od + be).

Эта же самая конструкция может быть использована для расширения любого поля, над которым многочлен х + 1 простой. Таким полем является, например, GF (7), и его можно расширить до поля GF (49) точно так же, как поле вещественных чисел до поля комплексных чисел, что и было формально проделано перед доказательством последней теоремы.

С другой стороны, многочлен х + 1 не является простым многочленом над полем GF (5) и не может быть использован для его расширения. Чтобы построить расширение GF (25) поля GF (S), надо воспользоваться многочленом х + х + 1, который является простым над GF (5). При этом модуле правило умножения приобретает вид

(а + хЬ) (с - xd) = (ас - bd) + x (ad + be - bd).

Умножение в этом поле отлично от умножения в комплексном поле. Умножение всегда будет задаваться этим правилом, если поле GF (р -) получается как расширение поля GF (р) с помощью многочлена -Ь х -)- 1, и такое расширение всегда возможно, если х + X + \ является простым над GF (р). В частности, этот многочлен можно использовать при расширении GF (2) до GF (4).

При малых п круговые многочлены можно легко вычислить, разлагая многочлен х - 1. Очевидно, что ft (х) = х - 1. Для выяснения общей ситуации найдем несколько начальных многочленов. Пусть п = 2. Тогда

, х - 1 = (X 1) (X + 1) = Q, (X) Q, (X). Пусть (1 = 3. Тогда

X - 1 = (X - 1) (X + X + 1) = Q, (X) Q, (X). Пусть п = 4. Тогда

х 1 = (X - 1) (X + I) (х + 1) = Q, (X) Q, (X) Q. (X).

Отметим, что на каждом шаге появляется только один новый множитель. Пусть л = 5. Тогда

ж 1 = (X 1) (ж4 + х= + х + X + 1) = (X) Qb (X).

Пусть п = 6. Тогда

х - I = (X - 1) (X -f 1) (хЧ- X + 1) (X - X -(- 1) =

= Q. М Q> W Qs (X) Q, (X). Пусть n = 7. Тогда

х - 1 = (X - 1) (х + х= + X* + х + г + X -f 1) = =Qi (X) Q, (X). Пусть n = 8. Тогда

х - 1 = (X - 1) (X + 1) (X + 1) (х -f 1) = = Qi (X) Q, (X) Q, (x) Q, (X). Пусть n = 9. Тогда

x - 1 = (X - 1) (x + X + 1) (x + x + 1) = = Qi {X) Qs (X) Q. (X). Общий случай описывается следующей теоремой. Теорема 5.5.2. Для каждого п

deg (? (х) = Ф (п), где ф (п) - функция Эйлера.

Доказательство, ф (л) определяется как число целых чисел, меньших п и взаимно простых с л, и это в точности совпадает с числом линейных множителей, входящих в определение Q (х).П

Теорема S.5.3. Для каждого п

х -1 = П Q(x).

НОСТИ двух элементов зависит от основного поля. Два элемента комплексного поля могут быть сопряженными относительно ноля рациональных чисел, но не быть сопряженными относительно поля вещественных чисел. Нщ1ример, минимальный многочлен над Q комплексного числа /i/2 равен х* - 2, а над R равен х* + Множество сопряженных с j V2 элеме21тов, содержащее этот элемент, относительно поля Q равно {\/2, -т/Т, j 2, -jV2], а относительно поля R равно {/i/2, -iV2]-

5.5. Круговые многочлены

Над произвольным полем F можно выписать разложение многочлена X - 1 в произведение его простых делителей: 1

х - \ = Pi (х) Рг (х) ... рк (х). Если F - поле рациональных чисел, то простые делители находятся сравнительно легко. Они представляют собой многочлены, которые даются следующим определением.

Определение 5.5.1. Над произвольным полем F для каждого п круговой многочлен определяется равенством

е (х)= П (х-шУ,

НОД . п)=1

где С1) равно корню ) степени л из единицы в некотором расши-рении поля F.

Главным образом нас будут интересовать круговые многочлены над полем рациональных чисел Q. В этом случае ш = e-l принадлежит полю комплексных чисел, а для п< 105 коэффициентами круговых многочленов являются -1, О или +1.

В достаточно большом расширении поля F - для поля рациональных чисел таковым является комплексное поле - многочлен х - 1 может быть разложен в виде

х -1 = П (х-а>),

где о) - корень степени п из единицы. Следовательно, каждый круговой многочлен можно выразить в виде произведения некоторых из этих линейных множителей. Определение кругового ] многочлена специально построено так, чтобы все его коэффициенты были рациональными.

1) Имеется в виду, конечно, первообразный корень степени п из единицы. -J Прим. перед.