Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2020, 14:2, 308-320
Volume 27, No 2, 2020, P. 117-135
UDC 519.17
V. M. Fomichev and Ya. E. Avezova
Exact formula for exponents of mixing digraphs for register transformations
Abstract:
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.
DOI: 10.33048/daio.2020.27.670
Vladimir M. Fomichev 1,2,3,4
Yana E. Avezova 2
1. Financial University under the Government of Russian Federation,
49 Leningradskii Avenue, 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 Bld. 2 Vavilov Street, 119333 Moscow, Russia
4. Security Code LLC,
10 Bld. 1 Pervyi Nagatinskii Driveway, 115230 Moscow, Russia
e-mail: fomichev.2016@yandex.ru, avezovayana@gmail.com
Received September 6, 2019
Revised September 27, 2019
Accepted February 19, 2020
References
[1] G. Frobenius, Über Matrizen aus nicht negativen Elementen, Berl. Ber., 456–477 (1912) [German].[2] A. L. Dulmage and N. S. Mendelsohn, The exponent of a primitive matrix, Can. Math. Bull. 5 (3), 241–244 (1962).
[3] V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva, and S. N. Kyazhin, Primitivity and local primitivity of digraphs and nonnegative matrices, Diskretn. Anal. Issled. Oper. 25 (3), 95–125 (2018) [Russian] [J. Appl. Ind. Math. 12 (3), 453–469 (2018)].
[4] V. M. Fomichev, Methods of Discrete Mathematics in Cryptology (Dialog-MIFI, Moscow, 2010) [Russian].
[5] V. Yu. Protasov, Semigroups of non-negative matrices, Usp. Mat. Nauk, No. 6, 191–192 (2010) [Russian] [Rus. Math. Surv. 65 (6), 1186–1188 (2010)].
[6] V. Yu. Protasov and A. S. Voynov, Sets of nonnegative matrices without positive products, Linear Algebra Appl. 437 (3), 749–765 (2012).
[7] A. S. Voynov, Shortest positive products of nonnegative matrices, Linear Algebra Appl. 439 (6), 1627–1634 (2013).
[8] R. A. Brualdi and B. Liu, Generalized exponents of primitive directed graphs, J. Graph Theory 14 (4), 483–499 (1990).
[9] B. Liu, Generalized exponents of Boolean matrices, Linear Algebra Appl. 373, 169–182 (2003).
[10] V. M. Fomichev and S. N. Kyazhin, Local primitivity of matrices and graphs, Diskretn. Anal. Issled. Oper. 24 (1), 97–119 (2017) [Russian] [J. Appl. Ind. Math. 11 (1), 26–39 (2017)].
[11] H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z. 52, 642–648 (1950) [German].
[12] P. Perkins, A theorem on regular graphs, Pac. J. Math. 11 (4), 1529–1533 (1961).
[13] A. L. Dulmage and N. S. Mendelsohn, Gaps in the exponent set of primitive matrices, Ill. J. Math. 8 (4), 642–656 (1964).
[14] S. W. Neufeld, A diameter bound on the exponent of a primitive directed graph, Linear Algebra Appl. 245, 27–47 (1996).
[15] A. V. Knyazev, Estimations for extreme values of principal metric characteristics of pseudosymmetrical graphs, Dr. Sci. Diss. (VTs RAN, Moscow, 2016) [Russian].
[16] V. M. Fomichev The new universal estimation for exponents of graphs, Prikl. Diskretn. Mat., No. 3, 78–84 (2016) [Russian].
[17] V. M. Fomichev On improved universal estimation of exponents of digraphs, Prikl. Diskretn. Mat., No. 43, 115–123 (2019) [Russian].
[18] S. W. Golomb Shift register sequences – A retrospective account, in Sequences and Their Applications (Proc. 4th Int. Conf. SETA–2006, Beijing, China, Sept. 24–28, 2006) (Springer, Heidelberg, 2012), pp. 1–4 (Lect. Notes Comput. Sci., Vol. 4086).
[19] M. Goresky and A. Klapper, Algebraic Shift Register Sequences (Camb. Univ. Press, Cambridge, 2012).
[20] V. I. Solodovnikov, Shift Registers and Cryptographic Algorithms Based on Them (Lambert Acad. Publ., Saarbrücken, 2017) [Russian].
