Оценка характеристик нелинейности композиций функций векторных пространств с помощью матрично-графового подхода

Развивается разработанный В. М. Фомичевым матрично-графовый подход к оценке характеристик нелинейности преобразований векторных пространств с помощью троичных матриц над мультипликативной полугруппой $\{0,1,2\}$ или орграфов, дуги которых помечены числами из $\{0,1,2\}$. Орграф $\Gamma$ с множеством вершин $\{1,\ldots ,n\}$ называется $\langle2\rangle$-примитивным, если при некотором натуральном $t$ для любых $i,j\in\{1,\ldots ,n\}$ найдётся путь из $i$ в $j$ длины $t$, проходящий через дугу с меткой $«2»$, наименьшее такое $t$ называется $\langle2\rangle$-экспонентом орграфа $\Gamma$ (обозначается $\langle2\rangle$-$\exp\Gamma$). Преобразованию $g(x_1,\ldots ,x_n)$ множества $V_n$ с координатными функциями $g_1(x_1,\ldots ,x_n),\ldots ,g_n(x_1,\ldots ,x_n)$ соответствует $n$-вершинный орграф $\Gamma_\Theta(g)$, где дуга $(i,j)$ помечена числом $0$, $1$ или $2$ тогда и только тогда, когда $g_j$ зависит от $x_i$ соответственно фиктивно, линейно или нелинейно, $1\le i,j\le n$. Преобразование $g$ называют вполне нелинейным, если метка каждой дуги орграфа есть $«2»$. Преобразование $g$ называется $\langle2\rangle$-перфективным, если при некотором натуральном $t$ все дуги орграфа $\Gamma_\Theta(g^t)$ помечены числом $«2»$, наименьшее такое $t$ называется показателем полной нелинейности преобразования $g$ (обозначается $\langle2\rangle$-$nlg$). Доказано: если в помеченном примитивном орграфе $\Gamma$ метка каждого простого контура содержит число $«2»$ и $\exp\Gamma=n$, то орграф $\Gamma$ является $\langle2\rangle$-примитивным и $\langle2\rangle$-$\exp\Gamma=\exp\Gamma$. Получена оценка $\langle2\rangle$-экспонента матрицы нелинейности $M$ порядка $2n$ раундовой функции блочных алгоритмов на основе сети Фейстеля с помощью $\langle2\rangle$-экспонента матрицы нелинейности $\Phi$ порядка $n$ функции усложнения: $\langle2\rangle$-$\exp M\le\langle2\rangle$-$\exp\Phi+2$. Эти результаты позволяют снизить сложность вычисления показателя полной нелинейности для некоторых преобразований $g$. Представлены алгоритмы распознавания полной нелинейности преобразования $g$ и оценки показателя $\langle2\rangle$-$nlg$. Для случайных преобразований средняя сложность не превышает $2\gamma(\gamma+1)\log8n$, где $\langle2\rangle$-$nlg=\gamma$ и элементарная операция есть вычисление любой функции на любом входном наборе. Алгоритм применён для получения точных значений $\langle2\rangle$-$nlg$ раундовых подстановок $g$ алгоритмов DES и Магма, получены значения $5$ и $6$ соответственно.