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

Все многочлены a_i(х) должны отличаться от всех многочле­нов b_i (х), так как в противном случае можно было бы сократить общие члены и получить многочлен меньшей степени, который можно разложить двумя разными способами.

Без потери общности предположим, что степень многочлена b₁(х) не больше степени многочлена а₁(х). Тогда

a₁(х) = b₁(х) Н(х) + s (х), где deg s(х)< deg b(х)< deg a(х). Далее,

s(x) а₂ (х) ... а_к(х) = b₁(х) { b₂ (х) ... b_l(х) — Н (х) а₂ (х) ... а_к(х)}

.
Разложим многочлен s(х) и многочлен, стоящий в квадратных скобках, на простые множители, разделив, если надо, на соответствующий элемент поля так, чтобы все множители были приведенными. Поскольку b₁ (х) не содержится в левой части, мы получили два различных разложения приведенного многочлена, степень которого меньше степени р (х). Это противоречие доказывает теорему.

В силу теоремы об однозначном разложении теперь ясно, что для любых двух многочленов

r(х) и b(х) НОД[r(х), b(х)] и НОК[r(х), b(х)] являются единственными, так как наибольший общий делитель равен произведению всех общих для r(х) и b(х) простых делителей, причем каждый делитель входит в наименьшей из степеней, в которых он входит в r(х) и в b(x), а наименьшее общее кратное равно произведению всех простых делителей, входящих либо в r (х), либо в b(х), причем*"каждый делитель входит в наибольшей из степеней, в которых он входит в r(х) или в b(х). Далее, любой многочлен, делящий как r(х), так и b(х), делит НОД{r(х), b (х)}, а любой многочлен, делящийся и на r(х), и на b(х), делится на НОК[r (х), b(х)].

Из алгоритма деления многочленов вытекает важное следствие, известнее под названием алгоритма Евклида для многочленов.

Теорема 2.3.6 ( алгоритм Евклида для многочленов). Наибольший общий делитель двух многочленов r(х) и s(х) над полем GF(q) можно вычислить с помощью итеративного приме­нения алгоритма деления. Если 0≤ deg r(x) ≤ deg s(x), то последовательность вычислений такова:

s(x) =Q₁(x) r(x) +r₁(x)

r(x) =Q₂(x) r₂ (x) +r₃(x)

r₁(x) =Q₃(x) r₂(x) +r₄(x)

.

r_п-1(x) =Q_n+1(x) r_п(x),

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

Тогда r_п(х) = а НОД [r(х), s(х)], где а некоторый скаляр.

Доказательство. Отправляясь от первого уравнения, видим, что НОД[r(х),s(х)] делит и делимое, и делитель, и, следовательно, остаток. Проводя это рассуждение далее по всем уравнениям, видим, что НОД[r(x), s(х)] делит r_n (х). Отправляясь от последнего уравнения, видим, что r_п(х) делит делитель и остаток, так что он делит и делимое. Проводя это рассуждение по всем уравнениям вплоть до первого, видим, что r_n(х) делит НОД [r(х), s(х)].Так как r_п(х) делит НОД[r(х),s(х)] и делится на него, то получаем утверждение теоремы.

Следствие 2.3.7. НОД[r(х), s(х) ] = а(х) r(х) + b(х) s(х), где а(х) и b(х) —многочлены над GF(q).

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

+	0 1	*	0 1
0 1	0 1 1 0	0 1	0 0 0 1

Для произвольного элемента β поля GF(q) можно вычислить значение многочлена над GF(q) в этой точке, подставив элемент β вместо неопределенной переменной. Например, пусть над GF(3)

р (х)=2x⁵+x⁴ +x² +2.-...Тогда получаем

р (0) = 2-О⁵ + О⁴ + О² + 2 = 2,

+	0 1 2 3	*	0 1 2 3
0 1 2 3	0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0	0 1 2 3	0 0 0 0 0 1 2 3 0 2 3 1 0 3 1 2

р(I)=2·1⁵+1⁴+1² + 2 = 0,

р (2) =2·2⁵ + 2⁴ + 2² + 2 = 2.

Рис2.1 Пример полей GF(2) и GF(4)

В случае поля вещественных чисел известной процедурой является вычисление значений многочлена в расширении этого поля; широко применяется вычисление значений многочлена с веществен­ными коэффициентами в поле комплексных чисел. Аналогично можно вычислять значения многочлена над GF(q) в расширении поля GF(q).Такое вычисление проводится подстановкой элементов из расширения поля вместо неопределенной переменной х и выполнения операций в расширении поля. Например, пусть над GF(2)

р (х) = х³ + х + 1.

Тогда (см. рис. 2.1) для элементов поля СР (4)имеем

р (0) = О³ + 0 + 1 = 1,

р (1) = I³ + 1 + 1 = 1,

р (2) = 2³ + 2 + 1 = 2,

р (3) = З³ + 3 + 1 = 3.

Если p(β) = 0, то элемент β называется корнем многочлена p(х) или корнем уравнения p(х) = 0. Многочлен не обязательно имеет корни в своем собственном поле. Многочлен

p(x)= х³ + х + 1 не имеет корней в GF(2), а также в GF(4).

Теорема 2.3.8. Элемент β является корнем многочлена р (х) тогда только тогда, когда (х- β) делит р (х). Более того, корнями многочлена р (х) степени п являются не более п элементов поля.

Доказательство. Согласно алгоритму деления, р (х) = (_Х - β) Q (х) + s(х),

где степень s(х) меньше единицы. Таким образом, s(х) является элементом поля s₀. Следовательно, 0 = р (β) = (β — β) Q (β) + s₀. и соответственно s(х) = s₀ = 0

Обратно, если х -β делит р (х), то

р (х) = (x - β) Q(х),

так что р (β)= (β -β) Q(β) = 0, и, таким образом, β — корень многочлена р (х).Разложим теперь многочлен р (х) в произведение элемента поля и простых множителей. Степень многочлена р (х) равна сумме степеней простых множителей, и для каждого корня имеется один такой множитель. Следовательно, существует не более п корней.

КИТАЙСКИЕ ТЕОРЕМЫ ОБ ОСТАТКАХ

Теорема 2.3.8. Для заданного множества попарно взаимно простых многочленов т₁ (х), m₂(х), ..., т_k (х) и множества многочленов с₁ (х), с₂ (х), ..., с_k (х), таких, что deg c_i(x) < deg m_i(x), система сравнена и

с₁ (х) = с (х) (mod m_i(x) i = 1, ..., k, имеет не более одного решения с (х}, удовлетворяющего условию

_k

dtg c(x<∑deg m_i (x.).

ⁱ⁼¹

Доказательство.. Предположим, что имеются два решения, а именно

c(x) = Q_i(x) m_i(x) +c_i(x)

и

c*(x) = Q_i^*(x) m_i(x) +c_i(x) ,

так что разность с(х) — с*(х) кратна многочлену т_{ (х) для каждого i. Тогда многочлен с(х) — с*(х) кратен и многочлену ∏^k_i=1 m_i(x), причем

deg [с(х) – с* (х)]<deg [ ∏^k m_i(x) ] ,

i=1

Следовательно, с(х) — с*(х) = О, и доказательство закончено.

Так же как и в кольце целых чисел, в кольце многочленов над произвольным полем выполняется равенство

НОД [r (х) , s(х)] = а (х) r(х) + b(х) s (х)

для некоторых а(х) и b(х). Для заданного множества попарно взаимно простых т_{ (х) положим М (х) = П^k_i=1 m_i (х) и М_i(х)=М(х)/т₁(х) и допустим, что N_i (х) и п_i (х) удовлетворяют ра­венствам N_i(х) М_i (х)+ п_i(х) т_i(х) = I; согласно следствию 2.3.7, такие многочлены N_{(х) и п_г (х) всегда существуют

Теорема 2.3..9. Пусть М(х) = ∏^k_i=1 m_i(x) - произведение попарно взаимно простых многочленов, и пусть М_i (х) = М (х)/т_i (х)

и N_i(х) удовлетворяют равенствам N_i(х) М_i (х)+ п_i(х) т_i(х) = I. Тогда единственным решением системы сравнений ,

с_i(х) = с (х) (mod mi(x)), i = 1, ..., k, является

_k

с(х)=∑_i=1 с_i(х} N_i(х) М_i (х) (mod М (х)).

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

с (х) = с_г (х) N _i (х) М_i (х) (mod m_i(x)),
ибо т_i (х) делит М_r (х), если r ≠ i. Наконец, так как

N_i(х) М_i (х)+ п_i(х) т_i(х) = I,

то N_i(х) М_i(х) = 1 (mod m_i(x)) и с(х) = с_i (х) (mod m_i(x)), что и завершает доказательство.

2.4. КОНЕЧНЫЕ ПОЛЯ, ОСНОВАННЫЕ НА КОЛЬЦАХ МНОГОЧЛЕНОВ

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

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

Произвольный элемент r(х) кольца F[х] можно отобразить в элемент кольца РF[х]/(р (х)) с помощью соответствия r(х) —R_{Р (Х)} [r (х)]. Два элемента a(х) и b(х) из F[х], отображаемые в один и тот же элемент из F[х]/(р(х)), называются сравнимыми: