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

UptoLike

ВУЗ: 

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

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

Рубрика: 

51
Сумма многочленов )(xf и )(xg определяется равенством
∑
=
+=+
n
i
i
ii
xbaxgxf
0
)()()(,
а
произведение многочленов
∑
=
=
m
i
i
i
xaxf
0
)(
и
∑
=
=
n
i
i
i
xbxg
0
)(
∑
+
=
=
nn
k
k
k
xcxgxf
0
)()(,
∑
=+
=
kji
iik
bac njmi
≤
≤
≤
≤
0,0.
Деление: многочлен g(x)
∈
F[x] делит многочлен f(x)
∈
F[x]
если существует
h(x)
∈
F[x] такой, что f(x)=g(x)
⋅
h(x).
Деление с остатком. Пусть g(x)
≠
0 – многочлен из F[x]
над полем
F. Тогда для каждого f(x)
∈
F[x] существуют такие
многочлены
q(x) и r(x)
∈
F[x], что
f(x)=q(x)⋅g(x)+r(x) (deg(r)<deg(g).
Простые элементы кольца многочленов F[x] обычно назы-
вают
неприводимыми многочленами.
Определение: Многочлен f(x)
∈
F[x] называется неприво-
димым над полем F или в кольце F[x], если он имеет положи-
тельную степень и равенство
f(x)=g(x)
⋅
h(x); g(x),h(x)
∈
F[x] мо-
жет выполнятся лишь в том случае, когда либо
g(x), либо h(x)
являются
постоянными многочленами (т.е. имеют степень
0≤n и являются константами).
Неприводимость многочлена существенным образом зави-
сит от того, над каким полем он рассматривается.
Примеры:
1.
Многочлен f(x)=x
2
-2
∈
Q неприводим над полем рацио-
нальный чисел
Q, но приводим над полем действительных чисел
R т.к. )2)(2(2
2
+−=− xxx .
2.
Многочлен f(x)=x
2
+x+1 неприводим над полем Галуа
GF(r) т.к. f(0)=f(1)=1, но приводим над его расширением GF(4).
Неприводимые многочлены играют важную роль в устрой-
стве кольца, т.к. каждый многочлен из
F[x] может быть пред-
ставлен, причем единственным способом, в виде произведения
неприводимых многочленов. Эти неприводимые многочлены
являются, по сути дела, аналогами простых чисел, через произ-
52
ведение которых можно выразить любое натуральное число
n>1
(
основная теорема арифметики).
В нашем дальнейшем изложении применительно к крипто-
системам особенный интерес будут представлять многочлены
неприводимые степени
n над простыми полями F
p
порядка p, где
p – простое число. Поиск всех неприводимых многочленов за-
данной степени
n над некоторым полем F
p
или GF(p) представ-
ляет собой очень сложную задачу. Французский математик Эва-
рист Галуа (1811 -1832гг) создал теорию (теорию поля Галуа),
доказывающую существование неприводимых многочленов
сколь угодно большой степени, но поиск таких многочленов -
очень сложная задача, и криптографические службы всего мира
ведут активную работу по поиску таких многочленов, но эти ра-
боты засекречены. Известен
неприводимый многочлен степени
x
61
+ x
3
+1, а для n>61 данных найти не удалось. Чтобы более
подробно осветить вопросы нахождения неприводимых много-
членов над конечными полями, вопросы разложения многочле-
нов на множители над конечными полями и связанные с ними
проблемы построение линейных рекуррентных последователь-
ностей над конечными полями, которые лежат в основе построе-
ния современных криптосистем, продолжим знакомство
с ос-
новными понятиями и элементами теории конечного поля.
Определение. Пусть F – произвольное поле и f(x)
∈
F[x].
Тогда замена переменной
x в многочлене f(x) произвольным
элементом
b
∈
F обращает этот многочлен в корректно опреде-
ленный элемент поля
F. Если f(x)=a
0
+a
1
x+...+a
n
x
n
∈
F[x] и b
∈
F,
то, заменяя
x на b, получаем элемент f(b)=a
0
+a
1
b+...+a
n
b
n
∈
F.
Элемент
f(b) называют значением многочлена f(x) при x=b. Если
в кольце
F[x] имеется какое -либо полиномиальное равенство, то
заменяя в нем
x на b
∈
F, получаем равенство в поле F. (Принцип
подстановки). Тогда: элемент
b
∈
F называют корнем (или ну-
лем) многочлена f(x)
∈
F[x], если при x=b f(b)=0.
Теорема
®
(устанавливает связь между корнями и де-
лимостью
). Элемент b
∈
F является корнем многочлена
f(x)
∈
F[x] тогда и только тогда, когда многочлен x -b делит f(x)
(т.е.
x -b
|
f(x)).

Страницы