The Exact Formula for the Exponents of the Mixing Digraphs of Register Transformations
Vladimir Mikhailovich Fomichev, Ya. E. Avezova · Journal of Applied and Industrial Mathematics · 2020
A digraph is primitive if some positive degree of it is a complete digraph, i.e. has all possible arcs. The smallest degree of this kind is called the exponent of the digraph. Given a primitive digraph, the elementary local exponent for some vertices $$u$$ and $$v $$ is the least positive integer $$\gamma $$ such that there exists a path from $$u $$ to $$v$$ of any length not less than $$\gamma $$ . For the transformation on the binary $$n $$ -dimensional vector space which is given by a set of $$n $$ coordinate functions, there corresponds some $$n $$ vertex digraph such that a pair $$(u,v) $$ is an arc if the $$v $$ th coordinate component of the transformation depends essentially on the $$u$$ th variable. Such a digraph we call a mixing digraph of the transformation. Under study are the mixing digraphs of $$n$$ -bit shift registers with a nonlinear Boolean feedback function (NFSR), $$n>1 $$ , which are widely used in cryptography. We find the exact formulas for the exponent and elementary local exponents of the $$n $$ -vertex primitive mixing digraph associated to an NFSR. The above results can be applied to evaluating the length of the blank run of the pseudo-random sequences generators based on NFSRs.