О СЛОЖНОСТИ МЕТОДА ФОРМАЛЬНОГО КОДИРОВАНИЯПРИ АНАЛИЗЕ ГЕНЕРАТОРАС ПОЛНОЦИКЛОВОЙ ФУНКЦИЕЙ ПЕРЕХОДОВ | Прикладная дискретная математика. 2009. № 3(5).

Исследованы генераторы гаммы (автономные автоматы), множество состояний которых есть пространство двоичных n-мерных векторов, и функция переходов реализует полноцикловую подстановку множества состояний. Оценивается сложность Т_п решения системы уравнений гаммообразования (без ограничения на число уравнений) относительно неизвестного начального состояния методом формального кодирования. Оценка получена с помощью определения линейной сложности и порядка множества мономов для последовательности выходных функций генератора. Показано, что TL(2^n-1) < Т_п < TL(2ⁿ), где TL(m) - сложность решения над GF(2) системы из m линейных уравнений от m неизвестных. Данный класс генераторов порождает, в частности, нормальные рекуррентные последовательности над полем GF(2) (последовательности де Брёйна).