Geodesic
On complexity of formal coding method for analysis of generator with monocycle substitutional transition function
Prikladnaâ diskretnaâ matematika, no. 10 (2009), pp. 32-34 
V. M. Fomichev. On complexity of formal coding method for analysis of generator with monocycle substitutional transition function. Prikladnaâ diskretnaâ matematika, no. 10 (2009), pp. 32-34. http://geodesic.mathdoc.fr/item/PDM_2009_10_a15/
@article{PDM_2009_10_a15,
     author = {V. M. Fomichev},
     title = {On complexity of formal coding method for analysis of generator with monocycle substitutional transition function},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {32--34},
     year = {2009},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2009_10_a15/}
}
TY  - JOUR
AU  - V. M. Fomichev
TI  - On complexity of formal coding method for analysis of generator with monocycle substitutional transition function
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2009
SP  - 32
EP  - 34
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/PDM_2009_10_a15/
LA  - ru
ID  - PDM_2009_10_a15
ER  - 
%0 Journal Article
%A V. M. Fomichev
%T On complexity of formal coding method for analysis of generator with monocycle substitutional transition function
%J Prikladnaâ diskretnaâ matematika
%D 2009
%P 32-34
%N 10
%U http://geodesic.mathdoc.fr/item/PDM_2009_10_a15/
%G ru
%F PDM_2009_10_a15

Voir la notice de l'article provenant de la source Math-Net.Ru

Autonomous automata are investigated where automaton states are binary $n$-dimensional vectors and transition function releases monocycle substitution. The complexity $T_{n}$ of solving gamma generator equations system by formal coding method is estimated assuming the number of equations is not constrained. Bounds of $T_n$ are obtained by estimating line complexity and monomial sets order for output functions sequence. It is stated that $\mathrm{TL}(2^{n-1}), where $\mathrm{TL}(m)$ is the complexity of solving linear equations system of size $m\times m$ over field $\mathrm{GF}(2)$.

[1] Fomichev V. M., Diskretnaya matematika i kriptologiya, DIALOG-MIFI, M., 2003

[2] Shamir A., Patarin J., Courtois N., and Klimov A., “Efficient Algorithms for solving Overdefined Systems of Multivariate Polynomial Equations”, Eurocrypt'2000, LNCS, 1807, Springer, 2001, 392–407 | MR