Теоретические основы прикладной дискретной математики
О перемешивающих графах нелинейных подстановок двоичных регистров сдвига
В. С. Григорьевab a Финансовый университет при Правительстве РФ, г. Москва
b Отдел безопасности сетевых приложений АО "Позитив Текнолоджиз", г. Москва
Аннотация:
Исследован класс
$R(n,m)$ подстановок
$n$-мерного векторного пространства, реализуемых двоичными регистрами левого сдвига длины
$n$ c одной обратной связью
$f(x_1,\dots,x_n)=x_1\oplus\psi(x_2,\dots,x_n)$, зависящей существенно от
$m$ переменных,
$3\le m\le n$. Получена двусторонняя оценка экспонента перемешивающих орграфов
$\Gamma(g)$ с множеством вершин
$V=\{1,2,\dots,n\}$ нелинейных подстановок
$g\in R(n,m)$:
$$
n+\left\lceil\frac{n-1}{m-1}\right\rceil-1\le\exp{\Gamma(g)}\le\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1,
$$
где
$D(g)=\{i_1,\dots,i_m\}$ – множество номеров существенных переменных функции обратной связи (ячеек съёма на регистре сдвига),
$1=i_1<\dots<i_m\le n$,
$m\le n$;
$\Delta(D)$ – наибольшее расстояние между соседними ячейками съёма на регистре сдвига: $\Delta(D)=\max\{i_2-i_1,\dots,i_m-i_{m-1},n-i_m\}$. Получены верхние оценки суммы и отношения экспонентов перемешивающих орграфов подстановки
$g$ из класса
$R(n,m)$ и обратной к ней подстановки
$g^{-1}$:
\begin{gather*}
\exp{\Gamma(g)}+\exp{\Gamma(g^{-1})}\le2\left(\Delta(D)+\left\lfloor\frac{n^2}m\right\rfloor\right)+i_m,\\
\frac{\exp{\Gamma(g)}}{\exp{\Gamma(g^{-1})}}\le\frac{\Delta(D)+n+\left\lfloor\frac{(n-2)^2}2\right\rfloor-1}{n+\left\lceil\frac{n-1}{m-1}\right\rceil-1}.
\end{gather*}
Ключевые слова:
матрично-графовый подход, перемешивающий граф преобразования, примитивный граф, экспонент орграфа, регистр сдвига, число Фробениуса.
УДК:
519.1
DOI:
10.17223/2226308X/11/1