Дискретная математика. Ерош И.Л - 122 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

122
Например: пусть
f(X) = f
0
+f
1
X; g(X) = g
0
+ g
1
X + g
2
X
2
.
Тогда
f(X) + g(X) = (f
0
+g
0
) + (f
1
+g
1
)X + g
2
X
2
;
f(X) · g(X) = (f
0
g
0
) + (f
0
g
1
+f
1
g
0
)X + (f
1
g
1
+f
0
g
2
)X
2
+ f
1
g
2
X
3
.
Отсюда видно, что при сложении степень результирующего много
члена равна максимальной степени слагаемых, а при умножении – сум
ме степеней перемножаемых многочленов.
Упражнения.
Сложить и перемножить следующие пары многочленов:
a) f(X) = f
0
+f
1
X + f
2
X
2
; g(X) = g
0
+ g
1
X + g
3
X
3
;
b) f(X) = f
1
X + f
2
X
2
+ f
5
X
5
; g(X) = g
0
+ g
1
X
1
+ g
4
X
4
;
c) f(X) = f
1
X + f
2
X
2
+ X
5
; g(X) = g
0
+ g
1
X
3
+ g
2
X
4
.
А теперь сделайте то же самое, если указано конечное числовое поле
(модуль):
d) f(X) = 2X + 3X
2
+ X
5
; g(X) = 4
+ 2X
3
+ X
4
, p = 7;
e) f(X) = 3X + 2X
2
+ 2X
5
; g(X) = 2
+ 4X
1
+ 3X
4
, p = 5.
Если рассматривать многочлены всех возможных степеней F(X), то
с такими операциями сложения и умножения множество многочленов
образует кольцо.
Для любых двух многочленов f(X) и g(X) существуют, и притом
единственные, многочлены a(X) и r(X), такие, что f(X) = a(X)g(X) + r(X),
где степень g > степени r. Переходя к сравнениям многочленов, полу
чаем
f(X) º r(X) mod (g(X)). (6.2)
Деление многочленов производится так же, как и деление целых
чисел. Следует только учитывать, что все операции выполняются в
поле F(p). Например, разделим многочлен g(X) = 1 + X + X
2
на f(X) =
= 1 + X в поле F(2):
+1( X + X
2
)+1( X)
X + X
2
X
1
В результате получим (1 + X + X
2
): (1 + X) = X, при этом в остатке
будет 1. Для деления удобнее записывать многочлены в обратном по
рядке, начиная со старшей степени. При вычислении в поле F(2) опе
рация сложения имеет специальное обозначение «Å» и называется
«сложение по модулю 2».

Страницы