Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2017, 11:1, 26-39
Volume 24, No 1, 2017, P. 97-119
UDC 519.17
V. M. Fomichev and S. N. Kyazhin
Local primitivity of matrices and graphs
Abstract:
We develop a matrix-graph approach to the estimation of the communicative properties of a system of connected objects. In particular, this approach can be applied to analyzing the mixing properties of iterative cryptographic transformations of binary vector spaces, i. e. dependence of the output block bits on the input bits. In some applied problems, the saturation of the connections between the objects corresponds to the required level if the matrix modeling the connections or its certain submatrix is positive (the graph modeling the connections or its certain subgraph is complete). The concepts of local primitivity and local exponents of a nonnegative matrix (graph) are introduced. These concepts generalize and expand the area of application as compared to the familiar concepts of primitivity and exponent. We obtain a universal criterion for the local primitivity of a digraph and both a universal bound for the local exponents and its refinements for various particular cases. The results are applied to analyzing the mixing properties of a cryptographic generator constructed on the basis of two shift registers.
Tab. 2, bibliogr. 12.
Keywords: primitive matrix, primitive graph, exponent, local primitivity of a matrix (graph), local exponent.
DOI: 10.17377/daio.2017.24.519
Vladimir M. Fomichev 1,2
Sergey N. Kyazhin 2,3
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. Special Development Center of the Ministry of Defence of the Russian Federation,
21 Svobody St., 125362 Moscow, Russia
e-mail: fomichev@nm.ru, s.kyazhin@kaf42.ru
Received 7 December 2015
Revised 9 June 2016
References
[1] K. G. Kogos and V. M. Fomichev, Positive properties of nonnegative matrices, Prikl. Diskretn. Mat., No. 4, 5–13, 2012 [Russian].[2] S. N. Kyazhin and V. M. Fomichev, On primitive sets of natural numbers, Prikl. Diskretn. Mat., No. 2, 5–14, 2012 [Russian].
[3] S. N. Kyazhin and V. M. Fomichev, Local primitiveness of graphs and nonnegative matrices, Prikl. Diskretn. Mat., No. 3, 68–80, 2014 [Russian].
[4] L. Ya. Okunev, Kratkii kurs teorii chisel (A Brief Course in Number Theory), Uchpedgiz, Moscow, 1956 [Russian].
[5] 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).
[6] R. A. Brualdi and B. Liu, Generalized exponents of primitive directed graphs, J. Graph Theory, 14, 483–499, 1990.
[7] Y. Huang and B. Liu, Generalized $r$-exponents of primitive digraphs, Taiwan. J. Math., 15, No. 5, 1999–2012, 2011.
[8] B. Liu, Generalized exponents of Boolean matrices, Linear Algebra Appl., 373, 169–182, 2003.
[9] Z. Miao and K. Zhang, The local exponent sets of primitive digraphs, Linear Algebra Appl., 307, 15–33, 2000.
[10] J. L. Ramírez Alfonsín, The Diophantine Frobenius Problem, Oxf. Univ. Press, Oxford, 2005 (Oxf. Lect. Ser. Math. Appl., Vol. 30).
[11] J. Shao, J. Wang, and G. Li, Generalized primitive exponents with complete characterizations of the extreme digraphs, Chin. Ann. Math., Ser. A, 15, No. 5, 518–523, 1994 [Chinese]. Translated in Chin. J. Contemp. Math., 15, No. 4, 317–324, 1994.
[12] J. Shen and S. Neufeld, Local exponents of primitive digraphs, Linear Algebra Appl., 268, 117–129, 1998.
