|
This article is cited in 1 scientific paper (total 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.
Citation:
V. S. Grigoriev, V. M. Fomichev, “On primitivity of mixing digraphs for substitutions of shift registers”, Prikl. Diskr. Mat. Suppl., 2017, no. 10, 14–16
Linking options:
https://www.mathnet.ru/eng/pdma334 https://www.mathnet.ru/eng/pdma/y2017/i10/p14
|
|