Том 25, номер 2, 2018 г., Стр. 124-143

УДК 519.17
Фомичёв В. М.
Полугрупповые и метрические характеристики локально примитивных матриц и орграфов

Аннотация:
Понятие локальной примитивности квадратной $0,1$-матрицы порядка $n$ обобщено на случай произвольной части матрицы, не обязательно являющейся прямоугольной подматрицей. Аналогичное обобщение выполнено для произвольного множества $B$ пар начальных и конечных вершин путей в $n$-вершинном орграфе, $B \subseteq$ {($i, j$) | $1 \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.

Ключевые слова: перемешивающая матрица, примитивная матрица, локально примитивная матрица, экспонент матрицы, циклическая полугруппа матриц.

DOI: 10.17377/daio.2018.25.584

Фомичёв Владимир Михайлович ^1,2,3
1. Финансовый университет при Правительстве РФ,
Ленинградский пр., 49, 125993 Москва, Россия
2. Национальный исследовательский ядерный университет «МИФИ»,
Каширское шоссе, 31, 115409 Москва, Россия
3. Институт проблем информатики ФИЦ ИУ РАН,
ул. Вавилова, 44, корп. 2, 119333 Москва, Россия
е-mail: fomichev@nm.ru

Статья поступила 3 июля 2017 г.
Исправленный вариант — 11 декабря 2017 г.

Литература

[1] Кяжин С. Н., Фомичев В. М. Локальная примитивность графов и неотрицательных матриц // Прикл. дискрет. математика. 2014. № 3. С. 68–80.

[2] Фомичев В. М. О характеристиках локально примитивных орграфов и матриц // Прикл. дискрет. математика. Прил. 2017. № 10. С. 96–99.

[3] Фомичев В. М., Задорожный Д. И., Коренева А. М., Лолич Д. М., Юзбашев А. В. Об алгоритмической реализации $s$-боксов. Докл. XIX Науч.-практ. междунар. конф. «РусКрипто-2017» (Московская область, 21–24 марта 2017 г.). http://www.ruscrypto.ru/resource/summary/rc2017/02_fomitchev_zadorozhny_koreneva_lolich_yuzbashev.pdf

[4] Фомичев В. М., Кяжин С. Н. Локальная примитивность матриц и графов // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 1. С. 97–119.

[5] Фомичев В. М., Мельников Д. А. Криптографические методы защиты информации. Ч. 1. Математические аспекты: учебник для академического бакалавриата (под ред. В. М. Фомичева). М.: Изд-во ЮРАЙТ, 2016. 209 с.

[6] Berger T. P., Francq J., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation to propose a new lightweight block cipher: Lilliput // IEEE Tran. Comput. 2016. Vol. 65, No. 7. P. 2074–2089.

[7] Berger T. P., Minier M., Thomas G. Extended generalized Feistel networks using matrix representation // Selected Areas in Cryptography. Rev. Selected Pap. 20th Int. Conf. SAC (Burnaby, Canada, Aug. 14–16, 2013). Heidelberg: Springer-Verl., 2014. (Lect. Notes Comput. Sci.; Vol. 8282).

[8] Brualdi R. A., Liu B. Generalized exponents of primitive directed graphs // J. Graph Theory. 1990. No. 14. P. 483–499.

[9] Huang Y., Liu B. Generalized r-exponents of primitive digraphs // Taiwan. J. Math. 2011. Vol. 15, No. 5. P. 1999–2012.

[10] Liu B. Generalized exponents of Boolean matrices // Lin. Algebra Appl. 2003. No. 373. P. 169–182.

[11] Miao Z., Zhang K. The local exponent sets of primitive digraphs // Lin. Algebra Appl. 2000. No. 307. P. 15–33.

[12] Shen J., Neufeld S. Local exponents of primitive digraphs // Lin. Algebra Appl. 1998. No. 268. P. 117–129.

[13] Suzaki T., Minematsu K. Improving the generalized Feistel // Fast Software Encryption Rev. Selected Pap. 17th Int. Workshop FSE (Seoul, Korea, Feb. 7–10, 2010). Heidelberg: Springer-Verl., 2010. P. 19–39. (Lect. Notes Comput. Sci.; Vol. 6147).