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

UptoLike

ВУЗ: 

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

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

Рубрика: 

34
умножении складывались по модулю n + 1. В этом случае степень ре
зультирующего полинома не будет превосходить n. В общем виде это
можно записать так: R(x)·Q(x) =... a
l
b
s
x
lÅsmod(n+1)
..., где l и s прини
мают все возможные значения от n до 0.
Например, пусть мы имеем полиномы степени не выше 4. Для кон
кретности возьмем произведение двух полиномов: R(x) = 3x
4
+2x
2
+ 5;
Q(x) = x
4
+ 4x
3
+ x. Тогда произведение полиномов R и Q будет иметь
вид (3x
4
+ 2x
4
+ 5)·(x
4
+4x
3
+ x) = 3x
8mod5
+ 2x
6mod5
+ 5x
4mod5
+12x
7mod5
+
+8x
5mod5
+ 20x
3mod5
+ 3x
5mod5
+ 2x
3mod5
+ 5x = 5x
4
+ 25x
3
+ 12x
2
+
+17x +11 (т. е. степень результирующего полинома не превосходит 4).
При такой операции умножения полиномов свойство замкнутости
множества относительно операции умножения будет выполнено. Лег
ко проверяется аксиома ассоциативности. Нейтральный элемент по ум
ножению e = 1 (точнее, нейтральный элемент равен полиному, у кото
рого все коэффициенты кроме a
0
равны 0, а a
0
= 1). Однако не для вся
кого полинома существует обратный, т. е. аксиома об обратном эле
менте на множестве U/0 не выполняется. Таким образом, множество
полиномов степени не выше n с введенными выше операциями сложе
ния и умножения образует кольцо. Оно называется кольцом полино+
мов степени не выше n.
Поля
Пусть на множестве U задано две операции: типа сложения «+» и типа
умножения «·». Множество U с операцией «+» пусть образует коммута
тивную группу с нейтральным элементом e = 0. А множество U/0 с опера
цией «·» также образует группу. Тогда (U, «+», «·») есть поле.
Примеры.
1. U – множество действительных чисел, на котором введены опе
рации «обычного» сложения и умножения. (U, +) – коммутативная
группа с нейтральным элементом e = 0. Множество (U/0, ´) – также
коммутативная группа. Следовательно, (U, +, ´) есть поле. Это поле
имеет бесконечное континуальное множество элементов и называется
полем действительных чисел.
2. Возьмем в качестве U конечную совокупность чисел: N = 0, 1, 2,
3, 4 и зададим две операции: Åmod5 и Ämod5. Как было показано
выше, пары (N, Åmod5) и (N/0, Ämod5) – коммутативные группы.
Следовательно, (N, Åmod5, Ämod5) есть поле с конечным числом эле
ментов. Обобщая полученный пример, можно утверждать, что для лю
бого простого числа p существует поле с конечным числом элементов
p = 0, 1, 2, 3,..., p–1. Такие поля называются полями Галуа и обозна
чаются GF(p) – поле Галуа с p элементами.
Определим теперь модели с двумя классами объектов.

Страницы