Exact formula for exponents of mixing digraphs~for~register~transformations

V. M. Fomichev ; Ya. E. Avezova

Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 117-135

Résumé

A digraph is primitive if some positive degree of it is a complete digraph, i. e. has all possible edges. The least 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 every length at least $\gamma$. For transformation on the binary $n$-dimensional vector space that is given by a set of $n$ coordinate functions, the $n$ vertex digraph corresponds such that a pair $(u,v)$ is an edge if the $v$th coordinate component of transformation essentially depends on $u$th variable. Such a digraph we call a mixing digraph of transformation. We study the mixing digraphs of widely used in cryptography $n$-bit shift registers with nonlinear Boolean feedback function (NFSR), $n>1$. We find the exact formulas for the exponent and elementary local exponents for $n$-vertex primitive mixing digraph associated to NFSR. For pseudo-random sequences generators based on the NFSRs, our results can be applied to evaluate the length of blank run. Bibliogr. 20.

Détail

Keywords: mixing digraph, primitive digraph, locally primitive digraph, feedback shift register, exponent of a digraph.