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

Для регистра сдвига длины $n$, функция обратной связи которого зависит от двоичного знака управляющей последовательности (на каждом такте реализуется одно из двух регистровых преобразований), исследовано минимальное число $\gamma$ тактов регистра, после которых достигнуто полное перемешивание, то есть существенная зависимость каждой координатной функции композиции преобразований от всех переменных. Эффект полного перемешивания оценен с помощью множества $\hat{\Gamma}$ перемешивающих $n$-вершинных орграфов регистровых преобразований, имеющих общий гамильтонов контур. Дана оценка экспонента $\exp\hat{\Gamma}$ примитивного множества $\hat{\Gamma}$, которая позволяет оценить снизу число $\gamma$:
$$ \exp\hat{\Gamma}\leq 2n-2+\textstyle\sum\limits_{\alpha=0}^1\left(F(n-S(\phi_\alpha))+d_\alpha+s_{m(\alpha)}^\alpha\right), $$
где $S(\phi_\alpha)=\left\{s_1^\alpha,\ldots,s_{m(\alpha)}^\alpha\right\}$ — множество номеров существенных переменных функции обратной связи $\phi_\alpha(x_0,\ldots,x_{n-1})$; $n-S(\phi_\alpha)=\{n-s_j^\alpha: j=1,\ldots,m(\alpha)\}$; $d_\alpha=\text{НОД}\{n-S(\phi_\alpha)\}$; $F(n-S(\phi_\alpha))=d_\alpha\Phi((n-S(\phi_\alpha))/d_\alpha)$; $\Phi((n-S(\phi_\alpha))/d_\alpha)$ — число Фробениуса. Проведён вычислительный эксперимент при $n=6$ и $10$ по вычислению точного значения $\gamma$ с учётом управляющей последовательности. Установлено, что полное перемешивание возможно за число тактов, превышающее значение экспонента менее чем в $2$ раза.