Однонаправленная функция с секретом на базе КАМСИ

       

Тест для внешней (выходной) памяти


Основной инструмент для определения, имеет ли данная машина конечную выходную память – это модифицированная тестирующая таблица и ее тестирующий граф. Тестирующая таблица (для выходной памяти), состоит из двух частей, имеет q

столбцов O1O2…Oq, соответствующих различным значениям выходов. Строки верхней части имеют имена состояний таблицы переходов М.  На пересечении Si

строки и Оj

столбца записывается состояние, в которое будет переход из Si

при значении Оj

на выходе. Будем называть эти состояния Оj-премниками Si. Клетки верхней половины таблицы заполняются соответствующими преемниками. Верхняя часть таблицы называется таблицей выходных преемников (наследников).  Таким образом, машина М  Table 3а имеет

 

PS



NS,z

x=0

x=1

A

B,0

D,1

B

C,1

A,1

C

B.0

C,0

D

C,0

C,1

PS

z=0

z=1

A

B

D

B

-

(AC)

C

(BC)

-

D

C

C

AB

-

(AD)(CD)

AC

(BB)(BC)

-

AD

(BC)

(CD)

BC

-

-

BD

-

(AC)(CC)

CD

(BC)(CC)

-

a)

b)

c)

Table 3

выходные 1-преемники состояния В состояния А и С и не имеет ни одного 0-преемника. В Table 3b это соответствует заполнению строки В верхней половины таблицы. Для каждой пары состояний в нижней части таблицы записываются соответствующие преемники. Выходной Ок-преемники SiSj – парные сочетания выходных Ок-преемники из Si и Sj. Например, если преемниками из Si и Sj  есть SpSq  и SrSt,  соответственно, тогда их преемники имеют вид: SpSr, SpSt, SqSr

и SqSt.

Тестирующий (для выходной памяти) граф такой, что:

  • поставить в соответствие каждой строке нижней половины таблицы вершину графа и присвоить им имена этих строк.
  • соединить дугами вершины, которые в таблице являются в отношении источник-преемник.
  • Пример тестирующего графа приведен в Table 3с. Обратите внимание, что из вершины АВ выходит две дуги с одинаковыми значениями выхода, равного 1.

    Утверждение 2 Машина М имеет конечную выходную память, если и только если тестирующий граф не имеет циклов. Если граф, свободный от циклов, имеет наибольший путь длинной l, то М имеет выходную память порядка µ= l+1.

    В примере Table 3с граф свободен от цикла и наибольший путь AB=>AD=>CD=>BC равен 3, а порядок µ=4.

    Обратите внимание, что граф не содержит вершин с повторяющимися вхождениями, например, ВВ

    и т.д.. Наличие  таких пар не влияет на неопределенность.



    Содержание раздела