uzluga.ru
добавить свой файл

АНАЛИЗ АВТОМАТА ЭНО


О.В. Тубольцева


Институт прикладной математики и механики НАНУ, Донецк, Украина


Объект исследования – автомат Эно постраен на основе аналога отображения Эно [1] над конечным кольцом (p – простое чис-ло, ) [2]. Перейдем к величинам и операциям над кольцом и обозначим – операцию, обратную к (т.е. – вычитание по модулю ), полученная система определяет автомат Эно.

(1)

где параметры, – начальное состояние, , и внутренние, входные и выходные переменные.

В терминах теории автоматов [3] система (1) представляет собой инициальный автомат Мура , для которого , , функция переходов определена равенством

,

где вычисляется в соответствии с первым уравнением системы (1), а функция выходов определяется равенством

.

Для того, чтобы автомат Эно являлся БПИ автоматом, необходимо и достаточно, чтобы параметр был обратимым элементом кольца . Так как нас интересуют исследования автоматов Эно с позиции их использования в качестве потоковых шифров, то рассматриваем только БПИ автоматы.

Теорема 1. Диаметр графа переходов БПИ автомата Эно равен 2.

Следствие. БПИ автомат Эно – сильносвязный автомат.

Условие, когда БПИ автомат Эно является приведенным описано в теореме 2.

Теорема 2. БПИ автомат Эно является приведенным, тогда и только тогда, когда – обратимый элемент кольца , т.е. .

Следующая теорема дает возможность охарактеризовать в целом структуру классов эквивалентных состояний.

Теорема 3. Эквивалентные состояния БПИ автомата Эно являются решениями системы

(2)


Список литературы


  1. Кузнецов С.П. Динамический хаос. – М.: Физматлит, 2001. – 296с.

  2. Биркгоф Г., Барти Т. Современная прикладная алгебра. – М.: «Мир», 1976. – 400с.

  3. Трахтенброт Б.А., Барздинь Я.М. Конечные автоматы (поведение и синтез). – М.: «Наука», 1970. – 400с.

  4. Скобелев В.Г., Тубольцева О.В. Шифр на основе отображения Эно // Вестник Томского государственного университета. Приложение №14. 2005. С. 74–78.