Асимметричный криптографический алгоритм на базе Конечно-Автоматной Модели

         

КАМСИ-композиция и КАМСИ-примитив


Введем несколько определений.

Допустим, существует два примитива

и
, где i  и  j  –  i

-ый и j –ый примитивы типа

, а 
 - мощность множества
примитивов к-го типа.

Не трудно показать, что две КАМСИ-композиции, каждая из которых состоит из одинаковых примитивов

 и
, и отличаются только порядком расположения примитивов – имеют разные таблицы переходов. Одну из этих КАМСИ-композиций можно обозначить, например,
  и другую -
, где нижние индексы показывают позицию в КАМСИ-композиции. В математике такие последовательности называются кортежами.

В общем виде, m-позиционные кортежи у которых одинаковый набор типов КАМСИ-композиции можно записать в виде:

Форм. 16                                            

где:

- примитив типа q, который расположен в i-ой позиции кортежа;

 q - один из множества

примитивов типа q.([44])

Общее число m-позиционных кортежей, которые имеют одни и те же примитивы и отличаются только порядком их расположения равно ([45]):

Форм. 17                                                        

где:

 - множество примитивов типа w, один из которых  расположен в t-ой позиции кортежа.

Приступим к определению мощности множества примитивов.

Введем определение.

Два состояния А и В таблицы переходов, которые имеют вид

где C и D – любые состояния таблицы переходов,

будем называть взаимообратимыми. Взаимообратимые состояния имеют одинаковое заполнение в тестирующей таблице.   

Предварительно сформулируем несколько утверждений.

Утверждение 4: Таблица переходов КАМСИ не содержит взаимообратимых состояний.

Это утверждение вытекает из Theorem 14-1 цитированной выше книги Zvi Kohavi (стр. 510).

Утверждение 5: «Перестановка переходов в любой строке таблицы переходов КАМСИ сохраняет свойство КАМСИ и его тип (величину µ-задержки)».

Доказательство.

Первая часть Утверждения вытекает из способа построения тестирующей таблицы (см. «Switching and Finite Automata Theory», Zvi Kohavi), в которой каждой строке верхней половины тестирующей таблицы ставится  упорядоченное сочетание названий состояний переходов в соответствующей строке таблицы переходов. Из этого следует, что перестановка переходов сохраняет свойство КАМСИ.



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




Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий