Математические основы криптологии. Галуев Г.А. - 27 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

53
Определение. Пусть b
∈
F - корень многочлена f(x)
∈
F[x].
Кратностью корня b называют такое натуральное число
K=(1,2,...), что f(x) делится на (x -b)
K
, но не делится на (x -b)
K+1
.
При
K=1 корень называют простым, а при K>1 – кратным.
Определение. Производной многочлена
f(x)=a
0
+a
1
x+a
2
x
2
+...+a
n
x
n
∈
F[x] называется многочлен
f’(x)=a
1
+2a
2
x+...+na
n
x
n -1
∈
F[x]. Отсюда следует теорема.
Теорема. Корень b
∈
F многочлена f
∈
F[x] является крат-
ным тогда и только тогда, когда он одновременно является и
корнем производной
f’(x) многочлена f(x).
Существует связь между отсутствием или несуществова-
нием корней и неприводимостью многочленов. Если
f(x) - не-
приводимый многочлен из
F[x] степени n
≥
2, то согласно теоре-
ме
®
он не имеет корней в поле F. Обратное утверждение спра-
ведливо только для многочленов степени
2 и 3.
Теорема. Для неприводимости многочлена f(x)
∈
F[x] сте-
пени
2 и 3 в кольце F[x] необходимо и достаточно, чтобы он не
имел корней в поле
F.
Пример:
Пользуясь этой теоремой, можно найти неприво-
димые многочлены степени
2 и 3 в кольце F
2
[x] над конечным
полем
F
2
, путем исключения из всей совокупности многочленов
указанной степени, принадлежащих кольцу
F
2
[x], тех многочле-
нов, которые имеют корни в поле
F
2
. Напомним, что элементами
поля
F
2
или GF(r) являются {0,1}. Тогда очевидно, что в кольце
F
2
[x] имеется только один неприводимый многочлен степени 2:
f(x)=x
2
+x+1 и два неприводимых многочлена степени 3:
f(x)=x
3
+x+1, x
3
+x
2
+1.
Действительно: многочлены степени 2 – это
f
1
=x
2
+1,
f
2
=x
2
+x, f
3
=x
2
+x+1.
Подставляя в них вместо
x элементы в поля GF(r), т.е. 0
или
1, видно, что f
1
=0 при x=1, f
2
=0 при x=1 и x=0, а f
3
≠
0 при
любом
x
∈
{0,1}. Тоже самое и для многочленов степени 3:
f
1
=x
3
+x
2
+x+1, f
2
=x
3
+x
2
+1, f
3
=x
3
+x+1, f
4
=x
3
+x
2
+x, f
5
=x
3
+x
2
…
Наряду с многочленами
f(x) от одной переменной х, рас-
сматривают многочлены от нескольких переменных. Пусть
R -
коммутативное кольцо с единицей, и пусть
х
1
,...,х
n
символы, ко-
54
торые выступают в качестве переменных, образуем сначала
кольцо многочленов
R[x
1
], затем кольцо R[x
1,
x
2
]=R[x
1
]R[x
2
] и
т.д. пока не получим
R[x
1
,...,x
n
]=R[x
1
,...,x
n -1
]R[x
n
]. Элементами
кольца
R[x
1
,...,x
n
] являются выражения
f(x
1
,...,x
n
)=
∑
a
i1...in
x
1
i1
...x
n
in
с коэффициентами а
i1...in
∈
R, причем суммирование распро-
страняется на конечное множество
n наборов (i
1
,...,i
n
) неотрица-
тельных целых чисел и соблюдается соглашение
x
j
0
=1, 1
⊆
j
⊆
n.
Такое выражение называют
многочленом от переменных
х
1
,...,х
n
над кольцом R. Два многочлена f и g из R[x
1
,...,x
n
] равны,
когда равны все соответствующие коэффициенты. При этом
предполагается, что переменные
х
1
,...,х
n
перестановочны друг с
другом, так что, например, выражения
x
1
х
2
х
3
и х
3
х
1
х
2
отожде-
ствляются.
Определение. Пусть многочлен f(х
1
,...,х
n
)
∈
R[x
1
,...,x
n
] за-
дан выражением
f(x
1
,...,x
n
)=
∑
a
i1...in
x
1
i1
...x
n
in
.
Если a
i1...in
≠
0,то a
i1...in
x
1
i1
...x
n
in
называется членом много-
члена
f(x
1
,...,x
n
), а i
1
+...+i
n
- степенью этого члена. Степень мно-
гочлена
f(x
1
,...,x
n
) (deg(f)) определяется как наибольшая из сте-
пеней его членов. Для
f(x
1
,...,x
n
)=0 полагают deg(f)= -
∝
. Если
f(x
1
,...,x
n
)=0 и все члены f имеют одну и туже степень, то много-
член
f называют однородным.
Определение. Многочлен f(x
1
,...,x
n
)
∈
R[x
1
,...,x
n
] называется
симметрическим, если для любой перестановки i
1
+...+i
n
целых
чисел
1,...,n выполняется равенство
f(x
i1
,...,x
in
)= f(x
1
,...,x
n
).
Введем несколько понятий, связанных с расширением по-
лей, о котором мы немного говорили ранее.
Пусть
F поле. Подмножество К поля F, которое само явля-
ется полем относительно операций поля
F, называется его под-
полем. В этом случае поле F называется расширением поля К.
Если K
≠
F, то К – собственное подполе поля F.
Если
К - подполе конечного поля F
p
при простом Р, то оно
должно по определению содержать элементы
0 и 1, а значит, и

Страницы