Geodesic
On complexity of formal coding method for analysis of generator with monocycle substitutional transition function
Prikladnaâ diskretnaâ matematika, no. 3 (2009), pp. 21-28 
V. M. Fomichev. On complexity of formal coding method for analysis of generator with monocycle substitutional transition function. Prikladnaâ diskretnaâ matematika, no. 3 (2009), pp. 21-28. http://geodesic.mathdoc.fr/item/PDM_2009_3_a2/
@article{PDM_2009_3_a2,
     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 = {21--28},
     year = {2009},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2009_3_a2/}
}
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  - 21
EP  - 28
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/PDM_2009_3_a2/
LA  - ru
ID  - PDM_2009_3_a2
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 21-28
%N 3
%U http://geodesic.mathdoc.fr/item/PDM_2009_3_a2/
%G ru
%F PDM_2009_3_a2

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

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

[1] Schaumüller-Bichl I., “Cryptanalysis of the Data Encryption Standard by a method of formal coding”, Cryptography, Proc. (Burg Feuerstein, 1982), LNCS, 149, 1983, 235–255 | Zbl

[2] Courtois N., Klimov A., Patarin J., Shamir A., “Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations”, LNCS, 1807, 2000, 392–407 | MR | Zbl

[3] Fomichëv V. M., Diskretnaya matematika i kriptologiya, DIALOG–MIFI, M., 2003, 400 pp.