Полугрупповые и метрические характеристики локально примитивных матриц и орграфов

Понятие локальной примитивности квадратной $0,1$-матрицы порядка $n$ обобщено на случай произвольной части матрицы, не обязательно являющейся прямоугольной подматрицей. Аналогичное обобщение выполнено для произвольного множества $B$ пар начальных и конечных вершин путей в $n$-вершинном орграфе, $B\subseteq\{(i,j)\mid1\le i,j\le n\}$. Установлена связь локального $B$-матрицы (орграфа) с такими её характеристиками, как циклическая глубина и период, число не примитивных матриц и число неидемпотентных матриц в мультипликативной полугруппе всех квадратных $0,1$-порядка $n$ и др. Для широкого класса орграфов, важного для криптографических приложений, получены критерий $B$-и верхняя оценка $B$-экспонента.
Введены новые метрические характеристики локально примитивного орграфа $\Gamma$: $k,r$-экспорадиус, $k,r$-экспоцентр, где $1\le k,r\le n$, и матэкс – матрица порядка $n$ всех локальных экспонентов орграфа $\Gamma$. Дан пример расчёта матэкса для $n$-вершинного орграфа Виландта. С использованием введённых характеристик предложена идея построения алгоритмически реализуемых $s$-боксов (элементов раундовых функций блочных шифров) с относительно широким диапазоном размеров. Табл. 2, ил. 1, библиогр. 13.