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

UptoLike

ВУЗ: 

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

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

Рубрика: 

73
тельство, что данный алгоритм сходится и позволяет привести к
нахождению всех
K сомножителей )(
x
f
.
Таким образом, в данном алгоритме задача вычисления
f
- разлагающих многочленов сводится к решению систем линей-
ных уравнений, путем их представления в матричной форме за-
писи.
Из представленного алгоритма видно, насколько трудоем-
кой является процедура разложения произвольных многочленов
над конечными полями заданной степени на произведение не-
приводимых многочленов. Этот факт и нашел широкое приме-
нение таких трудоемких задач при
построении различных крип-
тографических систем. С понятием многочленов и процедурами
их деления друг а друга тесно связаны вопросы формирования
линейных рекуррентных последовательностей над конечными
полями, которые находят широкое применение при создании по-
точных криптосистем. Поэтому рассмотрим вопросы формиро-
вания линейных рекуррентных последовательностей над конеч-
ными полями.
74
8. Элементы теории конечного поля. Линейные
рекуррентные последовательности над конечными
полями.
Результаты, полученные в теории линейных рекуррентных
последовательностей над конечными полями, находят в настоя-
щее время практическое применение для генерации последова-
тельностей псевдослучайных чисел с гарантированно хорошими
для криптографии свойствами и служат основой для построения
современных поточных криптосистем. Поэтому рассмотрим
принципы построения линейных рекуррентных последователь-
ностей и важнейшие теоретические результаты, связанные с
ни-
ми и полученные в рамках теории конечных полей.
Определение. Пусть к - натуральное число,
110
,...,,,
−k
aaaa
- заданные элементы конечного поля
q
F . По-
следовательность
,...,
10
ss элементов поля
q
F , удовлетворяю-
щая соотноше-
нию
aSaSaSaS
nknkknkkn
+
+
+
+
=
−+−−+−+ 02211
...
,
,...2,1=n называется линейной рекуррентной последователь-
ностью (ЛРП) K - го порядка над полем
q
F .
Первые члены
110
,...,,
−k
SSS
однозначно определяют всю
последовательность и называются
начальными значениями.
Такое соотношение еще называют
линейным рекуррентным
соотношением K - го порядка. Будем считать, что линейное ре-
куррентное соотношение
K - го порядка (К - го порядка над по-
лем
q
F ) называется однородным, если q=0, в противном случае
-
неоднородным.
Пример.
Пусть порядок К=4, тогда имеем линейную ре-
куррентную последовательность
4 порядка над полем
q
F
вида:
aSaSaSaSaS
nnnnn
+
+
+
+
=
++++ 01122334
.
В практическом плане линейные рекуррентные последова-
тельности реализуются на базе современных компьютерных сис-

Страницы