(1) Rd(х)[a(х)+b(x)]= Rd(х)[a(х)]+ Rd(х)[b(х)]
, (2 ) Rd(х)[a(х)b(x)]= Rd(х)[ Rd(х)[a(х)] Rd(х)[b(х)].]
Доказательствосводится к упражнению: использовать алгоритм деления для выражений в обеих частях равенства и приравнять остатки.
Подобно тому как часто бывает полезным представление положительных целых чисел в виде произведения простых сомножителей, часто бывает полезным представление приведенных много
членов в виде произведения простых многочленов.
Теорема 2.3.5 (теорема об однозначном разложении).Ненулевой многочлен p(х) над некоторым полем однозначно (с точностью до порядка следования множителей) разлагается в произведение элемента поля и простых многочленов над этим полем
Доказательство.Ясно, что входящим в произведение элементом поля должен быть коэффициент рп-1, где п-1 —степень многочлена р (х). Можно пренебречь этим элементом и доказывать теорему для приведенных многочленов.
Предположим, что теорема не верна. Пусть р (х) — приведенный многочлен наименьшей степени, для которого не верна теорема. Тогда имеются два разложения:
р (х) = а1 (х) а2 (х) ... ак(х) = b1(х) b2 (х) ... bl(х),,
где ai(х) и bi(х) — простые многочлены.
Все многочлены ai(х) должны отличаться от всех многочленов bi (х), так как в противном случае можно было бы сократить общие члены и получить многочлен меньшей степени, который можно разложить двумя разными способами.
Без потери общности предположим, что степень многочлена b1(х) не больше степени многочлена а1(х). Тогда
a1(х) = b1(х) Н(х) + s (х), где deg s(х)< deg b(х)< deg a(х). Далее,
s(x) а2 (х) ... ак(х) = b1(х) { b2 (х) ... bl(х) — Н (х) а2 (х) ... ак(х)}
.
Разложим многочлен s(х) и многочлен, стоящий в квадратных скобках, на простые множители, разделив, если надо, на соответствующий элемент поля так, чтобы все множители были приведенными. Поскольку b1 (х) не содержится в левой части, мы получили два различных разложения приведенного многочлена, степень которого меньше степени р (х). Это противоречие доказывает теорему.
В силу теоремы об однозначном разложении теперь ясно, что для любых двух многочленов
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) =Q1(x) r(x) +r1(x)
r(x) =Q2(x) r2 (x) +r3(x)
r1(x) =Q3(x) r2(x) +r4(x)
.
rп-1(x) =Qn+1(x) rп(x),
и процесс обрывается, как только получается равный нулю остаток..
Тогда rп(х) = а НОД [r(х), s(х)], где а некоторый скаляр.
Доказательство.Отправляясь от первого уравнения, видим, что НОД[r(х),s(х)] делит и делимое, и делитель, и, следовательно, остаток. Проводя это рассуждение далее по всем уравнениям, видим, что НОД[r(x), s(х)] делит rn (х). Отправляясь от последнего уравнения, видим, что rп(х) делит делитель и остаток, так что он делит и делимое. Проводя это рассуждение по всем уравнениям вплоть до первого, видим, что rn(х) делит НОД [r(х), s(х)].Так как rп(х) делит НОД[r(х),s(х)] и делится на него, то получаем утверждение теоремы.
Следствие 2.3.7.НОД[r(х), s(х) ] = а(х) r(х) + b(х) s(х), где а(х) и b(х) —многочлены над GF(q).
Доказательство.Последнее уравнение с ненулевым остатком в утверждении предыдущей теоремы дает выражение многочлена rп (х) через rп-1 (х) и _rn-2(х). Перебирая уравнения снизу вверх, исключаем сначала rп-1(х), затем rп-2(х), и т. д. и в конце концов получим выражение rп (х) только через r(х) и s(х).
| + | 0 1 | * | 0 1 |
| 0 1 1 0 | 0 0 0 1 |
Для произвольного элемента β поля GF(q) можно вычислить значение многочлена над GF(q) в этой точке, подставив элемент β вместо неопределенной переменной. Например, пусть над GF(3)
р (х)=2x5+x4 +x2 +2.-...Тогда получаем
р (0) = 2-О5 + О4 + О2 + 2 = 2,
| + | 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 0 0 0 0 1 2 3 0 2 3 1 0 3 1 2 |
| + | 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 0 0 0 0 1 2 3 0 2 3 1 0 3 1 2 |
р(I)=2·15+14+12 + 2 = 0,
р (2) =2·25 + 24 + 22 + 2 = 2.
| + | 0 1 | * | 0 1 |
| 0 1 1 0 | 0 0 0 1 |
| Рис2.1 Пример полей GF(2) и GF(4) |
| Рис2.1 Пример полей GF(2) и GF(4) |
В случае поля вещественных чисел известной процедурой является вычисление значений многочлена в расширении этого поля; широко применяется вычисление значений многочлена с вещественными коэффициентами в поле комплексных чисел. Аналогично мо жно вычислять значения многочлена над GF(q) в расширении поля GF(q).Такое вычисление проводится подстановкой элементов из расширения поля вместо неопределенной переменной х и выполнения операций в расширении поля. Например, пусть над GF(2)
р (х) = х3 + х + 1.
Тогда (см. рис. 2.1) для элементов поля СР (4)имеем
р (0) = О3 + 0 + 1 = 1,
р (1) = I3 + 1 + 1 = 1,
р (2) = 23 + 2 + 1 = 2,
р (3) = З3 + 3 + 1 = 3.
Если p(β) = 0, то элемент β называется корнем многочлена p(х) или корнем уравнения p(х) = 0. Многочлен не обязательно имеет корни в своем собственном поле. Многочлен
p(x)= х3 + х + 1 не имеет корней в GF(2), а также в GF(4).
Теорема 2.3.8.Элемент β является корнем многочлена р (х) тогда только тогда, когда (х- β) делит р (х). Более того, корнями многочлена р (х) степени п являются не более п элементов поля.
Доказательство.Согласно алгоритму деления, р (х) = (Х - β) Q (х) + s(х),
где степень s(х) меньше единицы. Таким образом, s(х) является элементом поля s0. Следовательно, 0 = р (β) = (β — β) Q (β) + s0. и соответственно s(х) = s0 = 0
Обратно, если х -β делит р (х), то
р (х) = (x - β) Q(х),
так что р (β)= (β -β) Q(β) = 0, и, таким образом, β — корень многочлена р (х).Разложим теперь многочлен р (х) в произведение элемента поля и простых множителей. Степень многочлена р (х) равна сумме степеней простых множителей, и для каждого корня имеется один такой множитель. Следовательно, существует не более п корней.