General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

Diskretn. Anal. Issled. Oper., 2017, Volume 24, Number 1, Pages 97–119 (Mi da865)  

This article is cited in 9 scientific papers (total in 9 papers)

Local primitivity of matrices and graphs

V. M. Fomichevab, S. N. Kyazhinbc

a Financial University under the Government of the Russian Federation, 49 Leningradsky Ave., 125993 Moscow, Russia
b National Research Nuclear University MEPhI, 31 Kashirskoe Highway, 115409 Moscow, Russia
c Special Development Center of the Ministry of Defence of the Russian Federation, 21 Svobody St., 125362 Moscow, Russia

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.


Full text: PDF file (388 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2017, 11:1, 26–39

Bibliographic databases:

UDC: 519.17
Received: 07.12.2015
Revised: 09.06.2016

Citation: V. M. Fomichev, S. N. Kyazhin, “Local primitivity of matrices and graphs”, Diskretn. Anal. Issled. Oper., 24:1 (2017), 97–119; J. Appl. Industr. Math., 11:1 (2017), 26–39

Citation in format AMSBIB
\by V.~M.~Fomichev, S.~N.~Kyazhin
\paper Local primitivity of matrices and graphs
\jour Diskretn. Anal. Issled. Oper.
\yr 2017
\vol 24
\issue 1
\pages 97--119
\jour J. Appl. Industr. Math.
\yr 2017
\vol 11
\issue 1
\pages 26--39

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Ya. E. Avezova, V. M. Fomichev, “Usloviya primitivnosti i otsenki eksponentov mnozhestv orientirovannykh grafov”, PDM, 2017, no. 35, 89–101  mathnet  crossref
    2. V. M. Fomichev, D. M. Lolich, A. V. Yuzbashev, “Algoritmicheskaya realizatsiya $s$-boksov na osnove modifitsirovannykh additivnykh generatorov”, PDM. Prilozhenie, 2017, no. 10, 102–104  mathnet  crossref
    3. V. M. Fomichev, “O kharakteristikakh lokalno primitivnykh orgrafov i matrits”, PDM. Prilozhenie, 2017, no. 10, 96–99  mathnet  crossref
    4. V. M. Fomichev, “Semigroup and metric characteristics of locally primitive matrices and graphs”, J. Appl. Industr. Math., 12:2 (2018), 243–254  mathnet  crossref  crossref  elib
    5. V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva, S. N. Kyazhin, “Primitivity and local primitivity of digraphs and nonnegative matrices”, J. Appl. Industr. Math., 12:3 (2018), 453–469  mathnet  crossref  crossref  elib
    6. V. M. Bobrov, S. M. Komissarov, “O svoistvakh dvukh klassov s-boksov razmera $16\times16$”, PDM. Prilozhenie, 2018, no. 11, 57–61  mathnet  crossref
    7. V. M. Fomichev, “Uluchshennaya formula universalnoi otsenki eksponenta orgrafa”, PDM. Prilozhenie, 2018, no. 11, 16–20  mathnet  crossref
    8. V. S. Grigorev, “O peremeshivayuschikh grafakh nelineinykh podstanovok dvoichnykh registrov sdviga”, PDM. Prilozhenie, 2018, no. 11, 6–9  mathnet  crossref
    9. A. M. Koreneva, “O peremeshivayuschikh i nelineinykh svoistvakh modifitsirovannykh additivnykh generatorov”, PDM. Prilozhenie, 2018, no. 11, 65–68  mathnet  crossref
  • Дискретный анализ и исследование операций
    Number of views:
    This page:238
    Full text:35
    First page:9

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020