EN|RU
About Journal
Editorial Board

Publishing Ethics
Author Guide Submission
 Prepare Your Manuscript
Peer review
Archive

English version:
Journal of Applied and Industrial Mathematics, 2018, 12:3, 453-469

Volume 25, No 3, 2018, P. 95-125

UDC 519.17
V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva, and S. N. Kyazhin
Primitivity and local primitivity of digraphs and nonnegative matrices

Abstract:
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.

Keywords: primitive digraph, primitive matrix, local primitivity, primitive set, exponent, local exponent.

DOI: 10.17377/daio.2018.25.595

Vladimir M. Fomichev 1,2,3
Yana E. Avezova 2
Alisa M. Koreneva 2
Sergey N. Kyazhin 2
1. Financial University under the Government of the Russian Federation,
49 Leningradsky Ave., 125993 Moscow, Russia
2. National Research Nuclear University MEPhI,
31 Kashirskoe Highway, 115409 Moscow, Russia
3. Institute of Informatics Problems of FRC CSC RAS,
44/2 Vavilova St., 119333 Moscow, Russia
e-mail: fomichev@nm.ru, avezovayana@gmail.com, alisa.koreneva@gmail.com, s.kyazhin@kaf42.ru

Received 16 October 2017
Revised 23 March 2018

References

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

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

[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 [Russian].

[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 [Russian]. Translated in J. Math. Sci., 191, No. 1, 4–9, 2013.

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

[6] A. M. Dorokhova and V. M. Fomichev, Improvement of exponent estimates for mixing graphs of bijective shift registers over a set of binary vectors, Prikl. Diskretn. Mat., No. 1, 77–83, 2014 [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 and V. M. Fomichev, Mixing properties of modified additive generators, Diskretn. Anal. Issled. Oper., 24, No. 2, 32–52, 2017 [Russian]. Translated in J. Appl. Ind. Math., 11, No. 2, 215–226, 2017.

[9] S. N. Kyazhin, On adaptation of digraph local primitiveness conditions and local exponent estimations, Prikl. Diskretn. Mat., No. 4, 81–98, 2016 [Russian].

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

[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 [Russian].

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

[13] V. N. Sachkov, Probabilistic converters and regular multigraphs. I, Tr. Diskretn. Mat., 1, 227–250, 1997 [Russian].

[14] V. N. Sachkov and V. E. Tarakanov, Kombinatorika neotritsatel’nykh matrits, TVP, Moscow, 2000 [Russian]. Translated under the title Combinatorics of Nonnegative Matrices, AMS, Providence, 2002 (Transl. Math. Monogr., Vol. 213).

[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., No. 1, 118–124, 2010 [Russian].

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

[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 [Russian].

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

[20] V. M. Fomichev, Computational complexity of the original and extended Diophantine Frobenius problem, Diskretn. Anal. Issled. Oper., 24, No. 3, 104–124, 2017 [Russian]. Translated in J. Appl. Ind. Math., 11, No. 3, 334–346, 2017.

[21] V. M. Fomichev and S. N. Kyazhin, Local primitivity of matrices and graphs, Diskretn. Anal. Issled. Oper., 24, No. 1, 97–119, 2017 [Russian]. Translated in J. Appl. Ind. Math., 11, No. 1, 26–39, 2017.

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

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

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

[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, No. 7, 2074–
2089, 2016.

[26] T. P. Berger, M. Minier, and G. Thomas, Extended generalized Feistel networks using matrix representation, in Selected Areas in Cryptography (Re?vis. Sel. Pap. 20th Int. Conf. SAC, Burnaby, Canada, Aug. 14–16, 2013), pp. 289–305, Springer, Heidelberg, 2014 (Lect. Notes Comput. Sci., Vol. 8282).

[27] U. Blöcher and M. Dichtl, Fish: A fast software stream cipher, in Fast Software Encryption (Proc. Camb. Secur. Workshop, Cambridge, UK, Dec. 9–11, 1993), pp. 41–44, Springer-Verl., Heidelberg, 1994 (Lect. Notes Comput. Sci., Vol. 809).

[28] V. D. Blondel, R. M. Jungers, and A. Olshevsky, On primitivity of sets of matrices, Automatica, 61, 80–88, 2015.

[29] R. A. Brualdi and B. Liu, Generalized exponents of primitive directed graphs, J. Graph Theory, 14, 483–499, 1990.

[30] A. L. Dulmage and N. S. Mendelsohn, The exponent of a primitive matrix, Can. Math. Bull., 5, 241–244, 1962.

[31] A. L. Dulmage and N. S. Mendelsohn, Gaps in the exponent set of primitive matrices, Ill. J. Math., 8, 642–656, 1964.

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

[33] G. Frobenius, Über Matrizen aus nicht negativen Elementen, Berl. Ber., 456–477, 1912 [German].

[34] J. C. Holladay and R. S. Varga, On powers of non-negative matrices, Proc. Am. Math. Soc., 9, 631, 1958.

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

[36] M. Lewin and Y. Vitek, A system of gaps in the exponent set of primitive matrices, Ill. J. Math., 25, No. 1, 87–98, 1981.

[37] B. Liu, Generalized exponents of Boolean matrices, Linear Algebra Appl., 373, 169–182, 2003.

[38] Z. Miao and K. Zhang, The local exponent sets of primitive digraphs, Linear Algebra Appl., 307, 15–33, 2000.

[39] S. W. Neufeld, A diameter bound on the exponent of a primitive directed graph, Linear Algebra Appl., 245, 27–47, 1996.

[40] P. Perkins, A theorem on regular graphs, Pac. J. Math., 2, 1529–1533, 1961.

[41] V. Yu. Protasov and A. S. Voynov, Sets of nonnegative matrices without positive products, Linear Algebra Appl., 437, No. 3, 749–765, 2012.

[42] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Clarendon Press, Oxford, 2005 (Oxf. Lect. Ser. Math. Appl., Vol. 30).

[43] B. Schneier, Applied Cryptography: Protocols, Algorithms, and Source Code in C, Wiley, New York, 1996. Translated under the title Prikladnaya kriptografiya: Protokoly, algoritmy, iskhodnye teksty na yazyke Si, Triumf, Moscow, 2002.

[44] J. Shen and S. W. Neufeld, Local exponents of primitive digraphs, Linear Algebra Appl., 268, 117–129, 1998.

[45] T. Suzaki and K. Minematsu, Improving the generalized Feistel, in Fast Software Encryption (Revis. Sel. Pap. 17th Int. Workshop FSE, Seoul, Korea, Feb. 7–10, 2010), pp. 19–39, Springer, Heidelberg, 2010 (Lect. Notes Comput. Sci., Vol. 6147).

[46] A. S. Voynov, Shortest positive products of nonnegative matrices, Linear Algebra Appl., 439, No. 6, 1627–1634, 2013.

[47] H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z., 52, 642–648, 1950 [German].
 © Sobolev Institute of Mathematics, 2015