EN|RU
English version: Journal of Applied and Industrial Mathematics, 2018, 12:3, 453-469 |
![]() |
Volume 25, No 3, 2018, P. 95-125 UDC 519.17
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 Received 16 October 2017 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 | |
![]() |
|