О примитивности перемешивающих подстановок регистров сдвига

Исследованы некоторые вопросы примитивности перемешивающих орграфов композиций регистровых подстановок и связь экспонентов прямой и обратной подстановок. Пусть $G(g)$ – перемешивающий орграф подстановки $g$ регистра левого сдвига длины $n$ и $\{i_1,\dots,i_m$ – множество номеров существенных переменных функции обратной связи. Установлено, что орграф $G(g)$ примитивный тогда и только тогда, когда примитивен орграф $G(g^{-1})$. При этом $\exp G(g)=\exp G(g^{-1})$, если $i_k+i_{m+2-k}=n+2$ для всех $k=2,\dots,m$. Для подстановки $g$ регистра правого сдвига длины $n$ с обратной связью $x_n\oplus\psi(x_1,\dots,x_{n-1})$ и подстановки $h$ регистра левого сдвига длины $n$ с обратной связью $x_1\oplus\phi(x_2,\dots,x_n)$ показано, что 1) множество дуг перемешивающего орграфа $G(gh)$ состоит из $n$ петель (по одной в каждой вершине) и дуг вида $(i,n)$, где $i\in\{1,\dots,n-1\}$, таких, что $x_i$ – существенная переменная функции $\psi(x_1,\dots,x_{n-1})\oplus\phi(x_1,\dots,x_{n-1})$; 2) множество дуг перемешивающего орграфа $G(hg)$ состоит из $n$ петель (по одной в каждой вершине) и дуг вида $(i,1)$, где $i\in\{2,\dots,n\}$, таких, что $x_i$ – существенная переменная функции $\psi(x_2,\dots,x_n)\oplus\phi(x_2,\dots,x_n)$. Для преобразования $g$ регистра правого сдвига длины $n$ с обратной связью $f(x_1,\dots,x_n)$ и треугольной подстановки $h$ множества $\{0,1\}^n$ показано, что если орграф $G(g)$ примитивный, то примитивными являются орграфы $G(g)\cdot G(h)$ и $G(h)\cdot G(g)$ и экспонент каждого из этих орграфов не превосходит $\exp G(g)$.