This article is cited in
1 paper
Theoretical Foundations of Applied Discrete Mathematics
On primitivity of mixing digraphs for substitutions of shift registers
V. S. Grigorievab,
V. M. Fomichevacde a Financial University under the Government of the Russian Federation, Moscow
b "Positive Technologies", Moscow
c National Engineering Physics Institute "MEPhI", Moscow
d Federal Research Center "Computer Science and Control" of Russian Academy of Sciences, Moscow
e "Security Code", Moscow
Abstract:
Let
$g$ and
$h$ be substitutions defined by binary feedback left- and right-shift registers
$R_l$ and
$R_r$ respectively on their sets of states,
$n$ be the length of each of these registers,
$f_l=x_1\oplus\phi(x_2,\dots,x_n)$ and
$f_r=x_n\oplus\psi(x_1,\dots,x_{n-1})$ be the feedback functions of
$R_l$ and
$R_r$ respectively, and
$i_1,\dots,i_m$ be the numbers of the register stages which are the inputs of the feedback in
$R_l$,
$1=i_1<i_2<\dots<i_m\leq n$. So
$x_{i_1},\dots,x_{i_m}$ are all essential variables of the function
$f_l$. Let
$G(s)$ be a mixing digraph for a substitution
$s\in\{g,h,gh,hg\}$. We prove the following statements: 1) suppose,
$g^{-1}=h$, then
$G(g)$ is primitive iff
$G(g^{-1})$ is primitive; in this case,
$\exp G(g)=\exp G(g^{-1})$ if
$i_k+i_{m+2-k}=n+2$ for all
$k\in\{2,\dots,m\}$; 2) the set of arcs in
$G(gh)$ consists of
$n$ loops (one at each vertex) and arcs
$(i,n)$,
$i\in\{1,\dots,n-1\}$, such that
$x_i$ is an essential variable of the function $\psi(x_1,\dots,x_{n-1})\oplus\phi(x_1,\dots,x_{n-1})$; 3) the set of arcs in
$G(hg)$ consists of
$n$ loops (one at each vertex) and arcs
$(i,1)$,
$i\in\{2,\dots,n\}$, such that
$x_i$ is an essential variable of the function
$\psi(x_2,\dots,x_n)\oplus\phi(x_2,\dots,x_n)$; 4) suppose,
$h$ is a triangular substitution on
$\{0,1\}^n$ and
$G(g)$ is primitive; then the digraphs
$G(g)\cdot G(h)$ and
$G(h)\cdot G(g)$ are also primitive; in this case the exponent of each of these digraphs does not exceed
$\exp G(g)$.
Keywords:
mixing digraph, primitive digraph, exponent of graph, shift register, triangle transformation.
UDC:
519.1
DOI:
10.17223/2226308X/10/4