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

UptoLike

ВУЗ: 

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

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

Рубрика: 

31
- простое число и
ap/ , то
)(mod1
1
pa
p
≡
−
. Это утверждение
очевидно, если вспомнить, что для простого числа р,
() 1pp
ϕ
=−
.Наименьшие из чисел
:1(mod),(,)1amam
γ
γ
≡
=
называется
показателем числа а по модулю m. Существование
таких чисел
γ
обеспечивается указанной выше теоремой Эйле-
ра. Если показатель числа
а по модулю m равен
δ
, то
(mod )aa m
γβ
≡
тогда и только тогда, когда
(mod )
γ
βδ
=
. Показа-
тель числа
а по модулю m является делителем числа
()m
ϕ
. Ес-
ли показатель числа
a по модулю m равен
δ
, то показатель числа
a
k
равен
(,)
Í
ÎÄ k
δ
для произвольного целого k. В частном слу-
чае, когда показатель числа
а по модулю m равен
ϕ
(m), то а на-
зывается
первообразным (примитивным) корнем по модулю m.
Если
р – простое число, и число а является первообразным кор-
нем по модулю
Р, то любой элемент b из множества чисел
1,2,…,р -1 имеет однозначное представление в виде
(mod )
x
ba P≡
для некоторого целого числа х
∈
{0,1,…,р -1}.
Число
х при этом называется дискретным логарифмом
(или
индексом) числа b по основанию а.
Сложность вычисления дискретных логарифмов совпадает
со сложностью нахождения разложения целого числа на простые
сомножители и имеют
exp сложность, что определяет широкое
применение таких задач при построении современных криптоси-
стем
Число
m называется псевдослучайным по основанию а, ес-
ли
1
1(mod )
m
ap
−
≡ и
(, ) 1am =
(р – простое число). Существуют
составные числа
m, являющиеся псевдослучайными для всех а,
взаимно простых с
m. Такие числа называются числами Кар-
майкла. Например,
561 3 11 17, 1105 5 13 17mm
=
=⋅ ⋅ = =⋅ ⋅ . Если t
различных оснований
а
1
,…,а
t
выбираются независимо и случай-
но, то составное число
m выдержит тест Ферма
1
1(mod )
m
am
−
≡
i=1,…,t с вероятностью 2
t
p
−
≤ .
Важное значение в теории чисел и для дальнейшего изло-
32
жения материалов лекционного курса имеет понятие многочлена
или полинома.
Многочленом называется выражение вида
2
01 2
0
() ...
n
ni
ni
i
f
xaaxax ax ax
=
=+ + ++ =
∑
0
i
ãäå a i n
≤
≤ - коэффициенты;
х – переменная;
n - степень многочлена, обозначаемая degf(x).
Для многочленов, также как и для чисел, могут быть вве-
дены арифметические операции. Два многочлена
∑
=
=
n
i
i
i
xaxf
0
)(
и
∑
=
=
n
i
i
i
xbxg
0
)(
равны тогда и только тогда, когда
ii
ba =
.
Сумма многочленов
f(x) и g(x) определяется равенством
∑
=
+=+
n
i
i
ii
xbaxgxf
0
,)()()(
а произведение
∑∑
==
==
m
i
n
j
j
j
i
i
xbxgиxaxf
00
)( )(
∑∑
=+
+
=
==⋅
kji
jik
nm
k
k
k
bacгдеxcxgxf ,)()(
0
.
Теорема. Пусть f(x) и g(x) многочлены, тогда
)).(deg())(deg())()(deg(
)))(deg()),(max(deg())()(deg(
xgxfxgxf
x
g
x
f
x
g
x
f
+=⋅
≤
+
.
Многочлен
f(х) делится на многочлен g(x), если существу-
ет многочлен
q(x) такой, что f(x)=q(x)g(x).
В этом случае говорят, что многочлен
g(x) делит много-
член
f(x), при этом g(x) - делитель многочлена f(x), а f(x) -
кратное многочлена g(x).
Для многочлена
f(x)=a
0
+a
1
x+…+a
n
x
n
коэффициент а
0
явля-
ется
постоянным членом т.е. константой. Многочлены степени

Страницы