Semigroup and metric characteristics of locally primitive matrices and graphs

V. M. Fomichev

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 2, pp. 124-143

Résumé

The notion of local primitivity for a quadratic $0,1$-matrix of size $n\times n$ is extended to any part of the matrix which need not be a rectangular submatrix. A similar generalization is carried out for any set $B$ of pairs of initial and final vertices of the paths in an $n$-vertex digraph, $B\subseteq\{(i,j)\colon1\le i,j \le n\}$. We establish the relationship between the local $B$-exponent of a matrix (digraph) and its characteristics such as the cyclic depth and period, the number of nonprimitive matrices, and the number of nonidempotent matrices in the multiplicative semigroup of all quadratic $0,1$-matrices of order $n$, etc. We obtain a criterion of $B$-primitivity and an upper bound for the $B$-exponent. We also introduce some new metric characteristics for a locally primitive digraph $\Gamma$: the $k,r$-exporadius, the $k,r$-expocenter, where $1\le k,r\le n$, and the matex which is defined as the matrix of order $n$ of all local exponents in the digraph $\Gamma$. An example of computation of the matex is given for the $n$-vertex Wielandt digraph. Using the introduced characteristics, we propose an idea for algorithmically constructing realizable $s$-boxes (elements of round functions of block ciphers) with a relatively wide range of sizes. Tab. 2, illustr. 1, bibliogr. 13.

Détail

Keywords: mixing matrix, locally primitive matrix, exponent of a matrix, cyclic matrix semigroup.
Mots-clés : primitive matrix

Bibliographie

[1] S. N. Kyazhin, V. M. Fomichev, “Local primitiveness of graphs and nonnegative matrices”, Prikl. Diskretn. Mat., 2014, no. 3, 68–80 (Russian)

[2] V. M. Fomichev, “On characteristics of local primitive matrices and digraphs”, Prikl. Diskretn. Mat. Prilozh., 2017, no. 10, 96–99 (Russian) | DOI

[3] Fomichev V. M., Zadorozhnyi D. I., Koreneva A. M., Lolich D. M., Yuzbashev A. V., “Ob algoritmicheskoi realizatsii $s$-boksov”, Dokl. XIX Nauch.-prakt. mezhdunar. konf. “RusKripto-2017” (Moskovskaya oblast, 21–24 marta 2017 g.) http://www.ruscrypto.ru/resource/archive/rc2017/files/02_fomitchev_zadorozhny_koreneva_lolich_yuzbashev.pdf

[4] V. M. Fomichev, S. N. Kyazhin, “Local primitivity of matrices and graphs”, J. Appl. Ind. Math., 11:1 (2017), 26–39 | DOI | DOI | MR | Zbl

[5] V. M. Fomichev, D. A. Melnikov, Cryptographic methods of information security. Part 1: Mathematical aspects, YURAIT, Moscow, 2016 (Russian)

[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., 65:7 (2016), 2074–2089 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 8282, Springer-Verl., Heidelberg, 2014, 289–305 | DOI | MR | Zbl

[8] Brualdi R. A., Liu B., “Generalized exponents of primitive directed graphs”, J. Graph Theory, 14 (1990), 483–499 | DOI | MR | Zbl

[9] Huang Y., Liu B., “Generalized $r$-exponents of primitive digraphs”, Taiwan. J. Math., 15:5 (2011), 1999–2012 | DOI | MR | Zbl

[10] Liu B., “Generalized exponents of Boolean matrices”, Lin. Algebra Appl., 373 (2003), 169–182 | DOI | MR | Zbl

[11] Miao Z., Zhang K., “The local exponent sets of primitive digraphs”, Lin. Algebra Appl., 307 (2000), 15–33 | DOI | MR | Zbl

[12] Shen J., Neufeld S., “Local exponents of primitive digraphs”, Lin. Algebra Appl., 268 (1998), 117–129 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 6147, Springer-Verl., Heidelberg, 2010, 19–39 | DOI | Zbl