Primitivity and local primitivity of digraphs and nonnegative matrices

V. M. Fomichev ; Ya. E. Avezova ; A. M. Koreneva ; S. N. Kyazhin

Diskretnyj analiz i issledovanie operacij, Tome 25 (2018) no. 3, pp. 95-125.

Résumé

The article surveys the main results on the primitivity and local primitivity of digraphs and matrices from the inception of this research area in 1912 by now. We review the universal and special criteria for primitivity and local primitivity as well as universal and special bounds on the exponents and local exponents of digraphs and matrices. We describe some cryptographic applications of this mathematical apparatus for analyzing the mixing properties of block ciphers and keystream generators. The new promising research directions are formulated in the study of primitivity and local primitivity of digraphs and matrices. Bibliogr. 47.

Détail

Keywords: primitive digraph, local primitivity, primitive set, exponent, local exponent.
Mots-clés : primitive matrix

Bibliographie

[1] Ya. E. Avezova, “On primitivity of some sets of shift registers mixing digraphs”, Prikl. Diskretn. Mat. Prilozh., 2017, no. 10, 60–62 (Russian)

[2] Ya. E. Avezova, V. M. Fomichev, “Combinatorial properties of rectangular 0,1-matrix systems”, Prikl. Diskretn. Mat., 2014, no. 2, 5–11 (Russian)

[3] Ya. E. Avezova, V. M. Fomichev, “Conditions of primitivity and exponent bounds for sets of digraphs”, Prikl. Diskretn. Mat., 2017, no. 35, 89–101 (Russian) | MR

[4] Yu. A. Al'pin, V. S. Al'pina, “Combinatorial properties of irreducible semigroups of nonnegative matrices”, J. Math. Sci., 191:1 (2013), 4–9 | DOI | MR | Zbl

[5] A. S. Voynov, Multidimensional equations of self-similarity and applications, Dr. Sci. Diss., Mosk. Gos. Univ., Moscow, 2016 (Russian)

[6] A. M. Dorokhova, V. M. Fomichev, “Improvement of exponent estimates for mixing graphs of bijective shift registers over a set of binary vectors”, Prikl. Diskretn. Mat., 2014, no. 1, 77–83 (Russian)

[7] A. V. Knyazev, Estimations for extreme values of principal metric characteristics of pseudosymmetrical graphs, Dr. Sci. Diss., VTs RAN, Moscow, 2016 (Russian)

[8] A. M. Koreneva, V. M. Fomichev, “Mixing properties of modified additive generators”, J. Appl. Ind. Math., 11:2 (2017), 215–226 | DOI | MR | Zbl

[9] S. N. Kyazhin, “On adaptation of digraph local primitiveness conditions and local exponent estimations”, Prikl. Diskretn. Mat., 2016, no. 4, 81–98 (Russian) | MR

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

[11] S. N. Kyazhin, V. M. Fomichev, “On local exponents of the mixing graphs for the functions realized by A5/1 type algorithms”, Prikl. Diskretn. Mat. Prilozh., 2015, no. 8, 11–13 (Russian)

[12] S. N. Kyazhin, V. M. Fomichev, “Mixing properties of 2-cascade generators”, Prikl. Diskretn. Mat. Prilozh., 2016, no. 9, 60–62 (Russian)

[13] V. N. Sachkov, “Probabilistic converters and regular multigraphs”, Tr. Diskretn. Mat., 1, 1997, 227–250 (Russian) | MR | Zbl

[14] V. N. Sachkov, V. E. Tarakanov, Combinatorics of Nonnegative Matrices, Transl. Math. Monogr., 213, AMS, Providence, 2002 | DOI | MR | MR | Zbl

[15] V. M. Fomichev, Methods of discrete mathematics in cryptology, Dialog-MIFI, Moscow, 2010 (Russian)

[16] V. M. Fomichev, “Properties of paths in graphs and multigraphs”, Prikl. Diskretn. Mat., 2010, no. 1, 118–124 (Russian)

[17] V. M. Fomichev, “The estimates for exponents of primitive graphs”, Prikl. Diskretn. Mat., 2011, no. 2, 101–112 (Russian)

[18] V. M. Fomichev, “Estimates for exponent of some graphs by means of Frobenius's numbers of three arguments”, Prikl. Diskretn. Mat., 2014, no. 2, 88–96 (Russian)

[19] V. M. Fomichev, “The new universal estimation for exponents of graphs”, Prikl. Diskretn. Mat., 2016, no. 3, 78–84 (Russian)

[20] V. M. Fomichev, “Computational complexity of the original and extended Diophantine Frobenius problem”, J. Appl. Ind. Math., 11:3 (2017), 334–346 | DOI | MR | Zbl

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

[22] V. M. Fomichev, D. A. Melnikov, Cryptographic methods of information security, in 2 pts, YURAYT, Moscow, 2016 (Russian)

[23] Anderson R., “On Fibonacci keystream generators”, Fast Software Encryption, Proc. 2nd Int. Workshop (Leuven Belgium, Dec. 14–16, 1994), Lect. Notes Comput. Sci., 1008, Springer, Heidelberg, 1995, 346–352 | DOI | Zbl

[24] Barghi A., Exponents of primitive digraphs, , (accessed Apr. 15, 2018) http://math.dartmouth.edu/~pw/M100W11/amir.pdf

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

[26] Berger T. P., Minier M., Thomas G., “Extended generalized Feistel networks using matrix representation”, Selected Areas in Cryptography, Rev. Sel. Pap. 20th Int. Conf. (Burnaby, Canada, Aug. 14–16, 2013), Lect. Notes Comput. Sci., 8282, Springer, Heidelberg, 2014, 289–305 | DOI | MR | Zbl

[27] Blöcher U., Dichtl M., “Fish: a fast software stream cipher”, Fast Software Encryption, Proc. Camb. Security Workshop (Cambridge, UK, Dec. 9–11, 1993), Lect. Notes Comput. Sci., 809, Springer, Heidelberg, 1994, 41–44 | DOI | Zbl

[28] Blondel V. D., Jungers R. M., Olshevsky A., “On primitivity of sets of matrices”, Automatica, 61 (2015), 80–88 | DOI | MR | Zbl

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

[30] Dulmage A. L., Mendelsohn N. S., “The exponent of a primitive matrix”, Can. Math. Bull., 5 (1962), 241–244 | DOI | MR | Zbl

[31] Dulmage A. L., Mendelsohn N. S., “Gaps in the exponent set of primitive matrices”, Ill. J. Math., 8 (1964), 642–656 | MR | Zbl

[32] Dulmage A. L., Mendelsohn N. S., “Graphs and matrices”, Graph Theory and Theoretical Physics, Acad. Press, London, 1967, 167–229 | MR

[33] Frobenius G., “Über Matrizen aus nicht negativen Elementen”, Berl. Ber., 1912 (1912), 456–477 (German) | Zbl

[34] Holladay J. C., Varga R. S., “On powers of non-negative matrices”, Proc. Amer. Math. Soc., 9 (1958), 631–634 | DOI | MR | Zbl

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

[36] Lewin M., Vitek Y., “A system of gaps in the exponent set of primitive matrices”, Ill. J. Math., 25:1 (1981), 87–98 | MR | Zbl

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

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

[39] Neufeld S. W., “A diameter bound on the exponent of a primitive directed graph”, Linear Algebra Appl., 245 (1996), 27–47 | DOI | MR | Zbl

[40] Perkins P., “A theorem on regular graphs”, Pac. J. Math., 2 (1961), 1529–1533 | DOI | MR

[41] Protasov V. Yu., Voynov A. S., “Sets of nonnegative matrices without positive products”, Linear Algebra Appl., 437:3 (2012), 749–765 | DOI | MR | Zbl

[42] Ramírez Alfonsín J. L., The Diophantine Frobenius problem, Oxf. Lect. Ser. Math. Appl., 30, Clarendon. Press, Oxford, 2005 | MR

[43] Schneier B., Applied cryptography: protocols, algorithms, and source code in C, John Wiley Sons, Inc., New York, 1996 | MR

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

[45] Suzaki T., Minematsu K., “Improving the generalized Feistel”, Fast Software Encryption, Rev. Sel. Pap. 17th Int. Workshop (Seoul, Korea, Feb. 7–10, 2010), Lect. Notes Comput. Sci., 6147, Springer, Heidelberg, 2010, 19–39 | DOI | Zbl

[46] Voynov A. S., “Shortest positive products of nonnegative matrices”, Linear Algebra Appl., 439:6 (2013), 1627–1634 | DOI | MR | Zbl

[47] Wielandt H., “Unzerlegbare nicht negative Matrizen”, Math. Z., 52 (1950), 642–648 | DOI | MR | Zbl