×

Primitivity and local primitivity of digraphs and nonnegative matrices. (Russian, English) Zbl 1413.05229

Diskretn. Anal. Issled. Oper. 25, No. 3, 95-125 (2018); translation in J. Appl. Ind. Math. 12, No. 3, 453-469 (2018).
Summary: 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. New promising research directions are formulated in the study of primitivity and local primitivity of digraphs and matrices.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments
15B33 Matrices over special rings (quaternions, finite fields, etc.)

Software:

Lilliput; Fish
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ya. E. Avezova, “On Primitivity of Some Sets of Shift Registers Mixing Digraphs,” Prikl. Diskretn. Mat. Prilozh. No. 10, 60-62 (2017).
[2] Ya. E. Avezova and V. M. Fomichev, “Combinatorial Properties of Rectangular 0, 1-Matrix Systems,” Prikl. Diskretn.Mat. No. 2, 5-11 (2014).
[3] Ya. E. Avezova and V. M. Fomichev, “Conditions of Primitivity and Exponent Bounds for Sets of Digraphs,” Prikl. Diskretn.Mat. No. 35, 89-101 (2017).
[4] Yu. A. Al’pin and V. S. Al’pina, “Combinatorial Properties of Irreducible Semigroups of Nonnegative Matrices,” Zap. Nauchn. Semin. POMI 405, 13-23 (2012) [J.Math. Sci. 191 (1), 4-9 (2013)]. · Zbl 1276.15015
[5] Voynov, A. S., Multidimensional Equations of Self-Similarity and Applications (2016), Moscow
[6] A. M. Dorokhova and V. M. Fomichev, “Improvement of Exponent Estimates forMixing Graphs of Bijective Shift Registers over a Set of Binary Vectors,” Prikl. Diskretn.Mat. No. 1, 77-83 (2014).
[7] Knyazev, A. V., Estimates for Extreme Values of Principal Metric Characteristics of Pseudosymmetrical Graphs (2002), Moscow
[8] A. M. Koreneva and V. M. Fomichev, “Mixing Properties of Modified Additive Generators,” Diskretn. Anal. Issled. Oper. 24 (2), 32-52 (2017) [J. Appl. Indust. Math. 11 (2), 215-226 (2017)]. · Zbl 1399.05149
[9] S. N. Kyazhin, “On Adaptation of Digraph Local Primitiveness Conditions and Local Exponent Estimations,” Prikl. Diskretn.Mat. No. 4, 81-98 (2016).
[10] S. N. Kyazhin and V. M. Fomichev, “Local Primitiveness of Graphs and Nonnegative Matrices,” Prikl. Diskretn.Mat. No. 3, 68-80 (2014).
[11] S. N. Kyazhin and V. M. Fomichev, “On Local Exponents of the Mixing Graphs for the Functions Realized by A5/1 Type Algorithms,” Prikl. Diskretn.Mat. Prilozh. No. 8, 11-13 (2015).
[12] S. N. Kyazhin and V. M. Fomichev, “Mixing Properties of 2-Cascade Generators,” Prikl. Diskretn. Mat. Prilozh. No. 9, 60-62 (2016).
[13] V. N. Sachkov, “Probabilistic Converters and Regular Multigraphs. I,” Trudy Diskretn. Mat. 1, 227-250 (1997). · Zbl 0947.68542
[14] V. N. Sachkov and V. E. Tarakanov, Combinatorics of Nonnegative Matrices (TVP,Moscow, 2000; AMS, Providence, 2002). · Zbl 1006.05001
[15] V. M. Fomichev, Methods of Discrete Mathematics in Cryptology (Dialog-MIFI, Moscow, 2010) [in Russian].
[16] V. M. Fomichev, “Properties of Paths in Graphs and Multigraphs,” Prikl. Diskretn. Mat. No. 1, 118-124 (2010).
[17] V. M. Fomichev, “Estimates for Exponents of Primitive Graphs,” Prikl. Diskretn. Mat. No. 2, 101-112 (2011).
[18] V. M. Fomichev, “Estimates for Exponent of Some Graphs by Means of Frobenius’s Numbers of Three Arguments,” Prikl. Diskretn.Mat. No. 2, 88-96 (2014).
[19] V. M. Fomichev, “The New Universal Estimation for Exponents of Graphs,” Prikl. Diskretn. Mat. No. 3, 78-84 (2016).
[20] V. M. Fomichev, “Computational Complexity of theOriginal and Extended Diophantine Frobenius Problem,” Diskretn. Anal. Issled. Oper. 24 (3), 104-124 (2017) [J. Appl. Indust. Math. 11 (3), 334-346 (2017)]. · Zbl 1399.11084
[21] V. M. Fomichev and S. N. Kyazhin, “Local Primitivity of Matrices and Graphs,” Diskretn. Anal. Issled.Oper. 24 (1), 97-119 (2017) [J. Appl. Indust.Math. 11 (1), 26-39 (2017). · Zbl 1374.05150
[22] V. M. Fomichev and D. A. Melnikov, Cryptographic Methods of Information Security, in 2 Parts (YURAYT, Moscow, 2016) [in Russian].
[23] Anderson, R., On Fibonacci Keystream Generators, 346-352 (1995), Heidelberg · Zbl 0939.94539
[24] A. Barghi, “Exponents of Primitive Digraphs,” available at http://math.dartmouth.edu/ pw/M100W11/amir.pdf (accessed April 15, 2018). · Zbl 1383.05249
[25] T. P. Berger, J. Francq, M. Minier, and G. Thomas, “Extended Generalized Feistel Networks Using Matrix Representation to Propose a New Lightweight Block Cipher: Lilliput,” IEEE Trans. Comput. 65 (7), 2074-2089 (2016). · Zbl 1360.94296
[26] Berger, T. P.; Minier, M.; Thomas, G., Extended Generalized Feistel Networks Using Matrix Representation, 289-305 (2014), Heidelberg · Zbl 1362.94020
[27] Blöcher, U.; Dichtl, M., Fish: A Fast Software Stream Cipher, 41-44 (1994), Heidelberg · Zbl 0943.94527
[28] V. D. Blondel, R. M. Jungers, and A. Olshevsky, “On Primitivity of Sets ofMatrices,” Automatica 61, 80-88 (2015). · Zbl 1337.15024
[29] R. A. Brualdi and B. Liu, “Generalized Exponents of Primitive Directed Graphs,” J. Graph Theory 14, 483-499 (1990). · Zbl 0714.05028
[30] A. L. Dulmage and N. S. Mendelsohn, “The Exponent of a Primitive Matrix,” Can. Math. Bull. 5, 241-244 (1962). · Zbl 0108.01203
[31] A. L. Dulmage and N. S. Mendelsohn, “Gaps in the Exponent Set of PrimitiveMatrices,” Illinois J. Math. 8, 642-656 (1964). · Zbl 0125.00706
[32] Dulmage, A. L.; Mendelsohn, N. S., Graphs and Matrices, 167-229 (1967), London · Zbl 0204.24402
[33] Frobenius, G., Über Matrizen aus nicht negativen Elementen, 456-477 (1912) · JFM 43.0204.09
[34] J. C. Holladay and R. S. Varga, “On Powers of Nonnegative Matrices,” Proc. Amer. Math. Soc. 9, 631 (1958). · Zbl 0096.00805
[35] Y. Huang and B. Liu, “Generalized r-Exponents of Primitive Digraphs,” Taiwan. J.Math. 15 (5), 1999-2012 (2011). · Zbl 1234.05152
[36] M. Lewin and Y. Vitek, “A SystemofGaps in the Exponent Set of PrimitiveMatrices,” Illinois J.Math. 25 (1), 87-98 (1981). · Zbl 0457.15014
[37] B. Liu, “Generalized Exponents of BooleanMatrices,” Linear Algebra Appl. 373, 169-182 (2003). · Zbl 1026.05050
[38] Z. Miao and K. Zhang, “The Local Exponent Sets of Primitive Digraphs,” Linear Algebra Appl. 307, 15-33 (2000). · Zbl 0991.05073
[39] S. W. Neufeld, “A Diameter Bound on the Exponent of a Primitive Directed Graph,” Linear Algebra Appl. 245, 27-47 (1996). · Zbl 0860.05038
[40] P. Perkins, “A Theorem on Regular Graphs,” Pacific J.Math. 2, 1529-1533 (1961). · Zbl 0103.00801
[41] V. Yu. Protasov and A. S. Voynov, “Sets of NonnegativeMatricesWithout PositiveProducts,” Linear Algebra Appl. 437 (3), 749-765 (2012). · Zbl 1245.15033
[42] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem (Clarendon Press, Oxford, 2005). · Zbl 1134.11012
[43] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C (Wiley, New York, 1996; Triumf, Moscow, 2002). · Zbl 0789.94001
[44] J. Shen and S. W. Neufeld, “Local Exponents of Primitive Digraphs,” Linear Algebra Appl. 268, 117-129 (1998). · Zbl 0886.05075
[45] Suzaki, T.; Minematsu, K., Improving the Generalized Feistel, 19-39 (2010), Heidelberg · Zbl 1279.94117
[46] A. S. Voynov, “Shortest Positive Products of Nonnegative Matrices,” Linear Algebra Appl. 439 (6), 1627-1634 (2013). · Zbl 1283.15111
[47] H. Wielandt, “Unzerlegbare, nicht negative Matrizen,” Math. Z. 52, 642-648 (1950). · Zbl 0035.29101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.