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



СТРУКТУРА И ПЕРИОДЫ ПРЕОБРАЗОВАНИЙ - часть 2


В условиях утверждения 1 в силу периодичности X® при всех i³N выполнено xi+1+xi+2+…+xi+T=yN+T -yN, и как следствие

yi+d×T = yi+d×(yN+T-yN) = yi.

Значит, N’<N и T’/d×T. Если N’<N-1, то yN-1+d×T=yN-1

и, следовательно, хN-1+d×T=хN-1, что противоречит условию.        

В условиях утверждения 2 порядок d элемента yT совпадает при всех i с порядками элементов xi+1+xi+2+…+xi+T. Поэтому при всех i

выполнено yi+d×T=yi, значит T’/d×T. При натуральных r имеем

yr×d×T = r×d×(x1+x2+…+xT) = r×d×yT = 0.                                           ¨

Рассмотрим  последовательность X® над X=Х1´…´Xп, в которой каждый член состоит из п компонент. Выделим в X® последовательность (над Хj) j-х компонент её членов. Обозначим её Xj® и назовём j-й координатной последовательностью последовательности X®, j=1,2,…,n.

С другой стороны, из последовательностей Xj®={xij} - над Хj, j=1,2,…,n, можно образовать последовательность X®={xi} над Х1´…´Xп, где xi=(xi1,…,xin), i=1,2,… Последовательность X® назовём сопряжением

последовательностей Х1®,…,Xп® (обозначается X®=Х1®*…*Xп®).

Очевидно, любая последовательность X® над X=Х1´…´Xп является сопряжением п координатных последовательностей. Из данных определений следует утверждение.

Утверждение 6.2. Последовательность X® над X=Х1´…´Xп является периодической с предпериодом N и периодом T тогда и только тогда, когда Xj® – периодическая последовательность с предпериодом Nj и периодом Tj, где N=max{N1,…,Nn}, T=НОК(T1,…,Tn).

Теорема 6.2. Если последовательность Y®={j(xi,1,…,xi,n)}

периода T получена с помощью отображения j:Х1´…´Xп®Y из периодических последовательностей Xj®={xij} над Хj с периодами Tj, j=1,…,n, то T делит НОК(T1,…,Tn). Если при этом отображение j биективно по всем переменным, то




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