О сложности метода формального кодирования при анализе генератора с полноцикловой функцией переходов

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