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



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


и указанного отображения y:

y×j(х)=y(х).                                                         (6.2)

Тогда для любого натурального t и любого xÎX:

y×jt(х) =

y(х),

а это с учётом полноцикловости преобразования j означает, что отображение y - константа. Имеем противоречие, из которого вытекает, что отображения y и y×j различны.

Пусть теперь j - неполноцикловое биективное преобразование множества X, и X’ – подмножество множества X, образующее некоторый цикл графа G(j). Определим отличное от константы отображение y:X®Y, где Y={y1,y2,…}: y(х)=y1

для всех хÎX’ и y(х)=y2

для всех хÎX\X’. При таком y для любого xÎX выполняется равенство (6.2). Следовательно, отображения y и y×j совпадают.                                                              ¨

Пусть j и y - преобразования множеств Х(n) и Х(n-1) соответственно, где |Х|=k и y задано подсистемой системы j:

j = {f1(x1,x2,...,xn-1),...,fп-1(x1,x2,...,xn-1),fп(x1,x2,...,xn)},

y = {f1(x1,x2,...,xn-1),...,fп-1(x1,x2,...,xn-1)}.

Рассмотрим критерий полноцикловости преобразования j. Каждому пути s=(s1,s2,…,st)

в графе G(y) поставим в соответствие преобразование d(s):

  d(s)=

,                                                   (6.3)

где для вершины а=(а1,а2,…,ап-1)ÎХ(n-1) графа G(y) под fn(a,xn)

понимается подфункция fn(а1,а2,…,ап-1,xn), реализующая преобразование множества Х.

Теорема 6.7. Преобразование j является п.ц. тогда и только тогда, когда y - п.ц. преобразование множества Х(n-1) и d(s) – п.ц. преобразование множества Х, где s - цикл в G(y).

Доказательство. Покажем корректность формулировки теоремы, ведь при п.ц. преобразовании y в качестве преобразования d(s) множества Х может быть рассмотрено kn-1

различных преобразований в зависимости от начала отсчёта вершин цикла s. Для этого убедимся, что при п.ц. преобразовании y все эти преобразования подобны.




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