Geodesic
Exact formula for exponents of mixing digraphs~for~register~transformations
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 117-135.

Voir la notice de l'article provenant de la source Math-Net.Ru

A digraph is primitive if some positive degree of it is a complete digraph, i. e. has all possible edges. The least degree of this kind is called the exponent of the digraph. Given a primitive digraph, the elementary local exponent for some vertices $u$ and $v$ is the least positive integer $\gamma$ such that there exists a path from $u$ to $v$ of every length at least $\gamma$. For transformation on the binary $n$-dimensional vector space that is given by a set of $n$ coordinate functions, the $n$ vertex digraph corresponds such that a pair $(u,v)$ is an edge if the $v$th coordinate component of transformation essentially depends on $u$th variable. Such a digraph we call a mixing digraph of transformation. We study the mixing digraphs of widely used in cryptography $n$-bit shift registers with nonlinear Boolean feedback function (NFSR), $n>1$. We find the exact formulas for the exponent and elementary local exponents for $n$-vertex primitive mixing digraph associated to NFSR. For pseudo-random sequences generators based on the NFSRs, our results can be applied to evaluate the length of blank run. Bibliogr. 20.
Keywords: mixing digraph, primitive digraph, locally primitive digraph, feedback shift register, exponent of a digraph. 
@article{DA_2020_27_2_a5,
     author = {V. M. Fomichev and Ya. E. Avezova},
     title = {Exact formula for exponents of mixing digraphs~for~register~transformations},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {117--135},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_2_a5/}
}
TY  - JOUR
AU  - V. M. Fomichev
AU  - Ya. E. Avezova
TI  - Exact formula for exponents of mixing digraphs~for~register~transformations
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 117
EP  - 135
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_2_a5/
LA  - ru
ID  - DA_2020_27_2_a5
ER  - 
%0 Journal Article
%A V. M. Fomichev
%A Ya. E. Avezova
%T Exact formula for exponents of mixing digraphs~for~register~transformations
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 117-135
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_2_a5/
%G ru
%F DA_2020_27_2_a5
V. M. Fomichev; Ya. E. Avezova. Exact formula for exponents of mixing digraphs~for~register~transformations. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 2, pp. 117-135. http://geodesic.mathdoc.fr/item/DA_2020_27_2_a5/

[1] Frobenius G., “Über Matrizen aus nicht negativen Elementen”, Berl. Ber., 1912, 456–477 (German) | Zbl

[2] Dulmage A. L., Mendelsohn N. S., “The exponent of a primitive matrix”, Can. Math. Bull., 5:3 (1962), 241–244 | DOI | MR | Zbl

[3] V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva, S. N. Kyazhin, “Primitivity and local primitivity of digraphs and nonnegative matrices”, J. Appl. Ind. Math., 12:3 (2018), 453–469 | DOI | MR | Zbl

[4] V. M. Fomichev, Methods of Discrete Mathematics in Cryptology, Dialog-MIFI, M., 2010 (in Russian)

[5] V. Yu. Protasov, “Semigroups of non-negative matrices”, Rus. Math. Surv., 65:6 (2010), 1186–1188 | DOI | DOI | MR | Zbl

[6] Protasov V. Yu., Voynov A. S., “Sets of nonnegative matrices without positive products”, Linear Algebra Appl., 437:3 (2012), 749–765 | DOI | MR | Zbl

[7] Voynov A. S., “Shortest positive products of nonnegative matrices”, Linear Algebra Appl., 439:6 (2013), 1627–1634 | DOI | MR | Zbl

[8] Brualdi R. A., Liu B., “Generalized exponents of primitive directed graphs”, J. Graph Theory, 14:4 (1990), 483–499 | DOI | MR | Zbl

[9] Liu B., “Generalized exponents of Boolean matrices”, Linear Algebra Appl., 373 (2003), 169–182 | DOI | MR | Zbl

[10] V. M. Fomichev, S. N. Kyazhin, “Local primitivity of matrices and graphs”, J. Appl. Ind. Math., 11:1 (2017), 26–39 | DOI | MR | Zbl

[11] Wielandt H., “Unzerlegbare, nicht negative Matrizen”, Math. Z., 52 (1950), 642-648 (German) | DOI | MR | Zbl

[12] Perkins P., “A theorem on regular graphs”, Pac. J. Math., 11:4 (1961), 1529–1533 | DOI | MR | Zbl

[13] Dulmage A. L., Mendelsohn N. S., “Gaps in the exponent set of primitive matrices”, Ill. J. Math., 8:4 (1964), 642–656 | DOI | MR | Zbl

[14] Neufeld S. W., “A diameter bound on the exponent of a primitive directed graph”, Linear Algebra Appl., 245 (1996), 27–47 | DOI | MR | Zbl

[15] A. V. Knyazev, Estimations for extreme values of principal metric characteristics of pseudosymmetrical graphs, Dr. Sci. Diss., VTs RAN, M., 2016 (in Russian)

[16] V. M. Fomichev, “The new universal estimation for exponents of graphs”, Prikl. Diskretn. Mat., 2016, no. 3, 78–84 (in Russian)

[17] V. M. Fomichev, “On improved universal estimation of exponents of digraphs”, Prikl. Diskretn. Mat., 2019, no. 43, 115–123 (in Russian)

[18] Golomb S. W., “Shift register sequences – A retrospective account”, Sequences and Their Applications – SETA 2006, Proc. 4th Int. Conf. (Beijing, China, Sept. 24–28, 2006), Lect. Notes Comput. Sci., 4086, Springer, Heidelberg, 2012, 1–4 | MR

[19] Goresky M., Klapper A., Algebraic shift register sequences, Camb. Univ. Press, Cambridge, 2012, 514 pp. | MR | Zbl

[20] V. I. Solodovnikov, Shift Registers and Cryptographic Algorithms Based on Them, Lambert Acad. Publ., Saarbrücken, 2017 (in Russian)