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

UptoLike

ВУЗ: 

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

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

Рубрика: 

33
0≤n
называются постоянными многочленами - константами.
Теорема (алгоритм деления многочленов с остатком)
Пусть
g(x)≠0 некоторый многочлен. Тогда для каждого
многочлена
f(x) существует также многочлены q(x) и r(x), что
() ()() ()
deg( ( )) deg( ( ))
fx qxgx rx
ãäå r x g x
=+
<
Пример:
1)(
)(
23
36
++=
+=
xxxg
xxxf
63 32
653 32
5
542
42
43
32
| 1
1()
xx xx
x
xx xxx qx
x
xxx
xx
xxx
xxx
+++
++ +++=
++
+
++
++
))(deg())(deg(
x
g
x
r
<
32
xxx++
)(1
x
r
x
=+
Пусть
f(х) – многочлен с целыми коэффициентами. Срав-
нение вида
f(х)≡0(mod m) называется сравнением с неизвестной
величиной. Задача о решении сравнения с неизвестной величи-
ной состоит в отыскании всех значений
х, которые ему удовле-
творяют.
Простейшее линейное сравнение имеет вид
ax
≡
b(mod m),
(
a,m)=1.
Теорема. Пусть d=НОД(a,m). Если d/b, то сравнение
ax
≡
b(mod m) будет иметь d решений вида:
,1,...,1,0 , mod))()((
0
−=+= dtm
d
m
tx
d
b
x
где
0
x - решение сравнения
)(mod1)( mx
d
a
=
. Если
bd
/
, то решений нет.
34
Пусть
n
n
xaxaaxf +++= ...)(
10
- многочлен с целы-
ми коэффициентами
).,...,1,0( niZa
i
=
Два решения
21
xиx сравнения n -ой степени )(mo
d
0)( m
x
f
≡
называют-
ся
эквивалентными, если
)(mod
21
mxx
≡
. Числа решений
сравнения определяется числом неэквивалентных решений.
Теорема. Пусть
r
mm ,...,
1
- попарно взаимно простые чис-
ла (т.е.
НОД(
ji
mm , )=1 для n
j
i ≤
<
≤
1 ) и
r
mmmm
⋅
⋅
⋅
= ...
21
. Тогда справедливо:
1.Сравнение
)(mod0)( m
x
f
≡
равносильно системе срав-
нений
)(mod0)(),...,(mod0)(
1 r
mxfmxf
≡
≡
2.Число решений сравнения
)(mo
d
0)( m
x
f
≡
равно про-
изведению числа решений отдельных сравнений указанной в п.1.
системы сравнений.
По аналогии с целыми числами можно ввести понятия
наибольшего общего делителя многочленов, наименьшего об-
щего кратного многочленов, взаимно простых и попарно вза-
имно простых многочленов, отношение сравнимости много-
членов и ряд других важнейших понятий.
Теорема. )(),...,(
1
xfxf
n
- многочлены, не все равные ну-
лю. Тогда существует однозначно определенный нормативный
многочлен
d(x), обладающий свойствами
1.
d(x) делит каждый многочлен
nixf
i
,...,1) , (
=
.
2.Любой многочлен
g(x), который делит каждый из много-
членов
),...,1), (( nixf
i
=
, делит и многочлен d(x).
Нормированный многочлен
d(x) называют наибольшим
общим делителем многочленов )(),...,(
1
xfxf
n
и обозначают
НОД( )(),...,(
1
xfxf
n
). Если НОД( )(),...,(
1
xfxf
n
)=1, то мно-
гочлены
)(),...,(
1
xfxf
n
называются взаимно простыми. Они
называются
попарно взаимно простыми, если
njixfxfНОД
ji
≤
<
≤
=
1, 1))(),((
.

Страницы