|
Рассмотрен асимметричный алгоритм кодирования на базе конечно-автоматной модели. Показано, что, если трудность взлома RSA определяется сложностью выполнения операции разложения числа на простые сомножители (это и приводит к необходимости использования ћдлинной арифметикиЋ), то для конечно-автоматной модели аналогичной операцией является декомпозиция кодера на простые компоненты. Показано, что сложность декомпозиции конечного автомата возрастает экспоненциально, в то время, как его быстродействие не зависит от размера его таблицы переходов. По аналогии с понятиями сложного и простого числа в теории чисел, введены понятия композиции конечных автоматов и примитивов. Особенность этих понятий заключается в том, что, сложное число в теории чисел представляет собой произведение простых чисел и это произведение не зависит от порядка расположения в нем сомножителей. Для конечного же автомата, эквивалентного композиции примитивов, имеют значение, как их набор, так и порядок их взаимного расположения в композиции, то есть, композиция автоматов не обладает свойством коммутативности. |