Дискретная математика и криптология



СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ


Многие криптографические системы используют для шифрования информации псевдослучайные последовательности, генерируемые программным способом. Качество шифрования определяется определёнными свойствами псевдослучайных последовательностей, в частности, их периодами. Так как порождение последовательностей большого периода основано на реализации многократных итераций преобразований, то для криптологии представляет интерес изучение структурных и периодических свойств преобразований конечных множеств.

6.1. Периоды последовательностей

Последовательность элементов множества X назовём последовательностью над X и обозначим X®.

Последовательность

X®={x1,x2,…,xi,…} над X называется периодической с предпериодом N и периодом T, если N+1 и T – наименьшие из натуральных чисел, при которых xi=xi+T

для всех i>N. Заметим, что если для всех i>N в xi=xi+t, то T/t.

Если N=0, то последовательность X®

называется чисто периодической с периодом T.

Утверждение 6.1. Если последовательность Y®={j(xi)} над Y получена с помощью отображения j:Х®Y из периодической последовательности X®={xi}

над Х с предпериодом N и периодом T, то Y® - периодическая с предпериодом N’ и периодом T’, где N’£N, T’ делит T.

Доказательство. Если xi=xi+Т, то и j(xi)=j(xi+Т), следовательно, N’£N и T’/T.       ¨    

Теорема 6.1. Для последовательностей X®={xi} и Y®={yi} над конечной аддитивной группой X, где yi=x1+x2+…+xi,

i=1,2,…, верны утверждения:

1. Если X® - периодическая с предпериодом N>0 и периодом T, то Y®

– периодическая с предпериодом N-1 и периодом T’, где T’/d×T и d есть порядок элемента yN+T-yN

группы X.

2. Если X® - чисто периодическая с периодом T, то Y® – чисто периодическая с периодом T’, где T’/d×T и d

есть порядок элемента yT группы X, при этом yr×d×T=0 при r=1,2,…

Доказательство. Из соотношения между членами последовательностей X® и Y® имеем:

yi+d×T  = yi+xi+1+xi+2+…+xi+d×T.




Содержание    Вперед