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

UptoLike

ВУЗ: 

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

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

Рубрика: 

77
цией или ЛРП, порожденной импульсом. Эта последователь-
ность обозначается
,...,
10
dd
и определяется начальными значе-
ниями
1,0...
1210
==
=
=
=
−− kk
dddd
(
1k ,1
0
=
=
приd
) и ли-
нейным рекуррентным соотношением
nknkknkkn
dadadad
02211
...
+
+
+
=
−+−−+−+
, (n=0,1,…)
Пример:
Пусть есть линейное рекуррентное соотношение
nnn
SSS +=
++ 15
, (n=0,1,…) над полем
2
F .
Устройство для ее реализации имеет вид:
Импульсная функция
,...,
10
dd
, соответствующая этому ре-
куррентному соотношению получается при начальном заполне-
ния регистра кодом
1 0 0 0 0
4321
=
=
=
=
=
++++ nnnnn
SSSSS
.
Тогда на выходе регистра получим ЛРП, порожденную
импульсом
с минимальным периодом
r=21.
Линейные рекуррентные последовательности над конеч-
ными полями тесно связаны с рассмотренными нами ранее мно-
гочленами.
Пусть
,...,
10
SS
однородная ЛРП К - го порядка над полем
q
F , удовлетворяющая рекуррентному соотношению:
nknkknkkn
SaSaSaS
02211
+
+
=
−+−−+−+
, (n=0,1,…) где
10
−
≤
≤∈ kjFa
qj
. Многочлен вида
][...)(
0
2
2
1
1
xFaxaxaxxf
q
k
k
k
k
k
∈−−−=
−
−
−
−
называется харак-
теристическим многочленом данной ЛРП. Его вид зависит толь-
78
ко от вида линейного рекуррентного соотношения.
Пример:
Пусть ЛРП над полем
2
F
определяется соотноше-
нием
,...1,0
12
=
+
=
++
nSSS
nnn
. Тогда соответствующий ей ха-
рактеристический многочлен имеет вид
1)(
2
−−= xxxf
.
Существует прямая связь между периодом ЛРП и поряд-
ком характеристического многочлена.
Теорема. Пусть
,...,
10
SS
- однозначная на ЛРП над полем
q
F и
][)( xFxf
q
∈
- характеристический многочлен этой по-
следовательности. Тогда линейный период этой последователь-
ности делит
))((
f
ord
, а минимальный период соответствую-
щей импульсной функции равен
))((
x
f
ord
.
Теорема. Пусть
,...,
10
SS
- однородная ЛРП над полем
q
F с
ненулевых вектором начального состояния. Пусть ее характери-
стический многочлен
][)( xFxf
q
∈
является неприводимым над
полем
q
F и удовлетворяет условию
0)0(
≠
f
. Тогда ЛРП
,...,
10
SS
является чисто периодической последовательностью и
ее минимальный период
))((
x
f
ord
r
=
.
Для практических приложений требуется формирование
ЛРП с как можно большим минимальным периодом. Каким об-
разом получить такую ЛРП отвечают следующие факты из тео-
рии конечного поля (мы уже знаем, что
max значение мини-
мального периода не превышает
1−
k
q
).
Определение. Однородная линейная рекуррентная после-
довательность над полем
q
F , характеристический многочлен
который является примитивным над этим полем
q
F , а вектор
начального состояния - ненулевым вектором, называется
после-
довательностью максимального периода над полем
q
F .
Это подтверждает следующая теорема.
Теорема. Каждая последовательность К - го порядка и мак-
симального периода над полем
q
F является чисто периодиче-

Страницы