Publication: The Exact Formula for the Exponents of the Mixing Digraphs of Register Transformations
Дата
2020
Авторы
Fomichev, V. M.
Avezova, Y. E.
Journal Title
Journal ISSN
Volume Title
Издатель
Аннотация
© 2020, Pleiades Publishing, Ltd.Abstract: A digraph is primitive if some positive degree of it is a complete digraph, i.e. has allpossible arcs. The smallest degree of this kind is called the exponent of the digraph. Given a primitive digraph, the elementarylocal exponent for some vertices u and v is the least positive integer γ such that there exists a path from u to v of any length not lessthan γ. For the transformation on the binary n-dimensional vector space which is given by a set of n coordinate functions, there corresponds some n vertex digraph such that a pair (u,v) is an arc if the vth coordinate component of the transformationdepends essentially on the u th variable. Sucha digraph we call a mixing digraph of the transformation.Under study are the mixing digraphs of n-bit shift registerswith a nonlinear Boolean feedback function (NFSR), n>1, which are widely used in cryptography. We findthe exact formulas for the exponent and elementary local exponents of the n-vertex primitive mixing digraph associated toan NFSR. The above results can be applied to evaluating the length of the blank run of thepseudo-random sequences generators based on NFSRs.
Описание
Ключевые слова
Цитирование
Fomichev, V. M. The Exact Formula for the Exponents of the Mixing Digraphs of Register Transformations / Fomichev, V.M., Avezova, Y.E. // Journal of Applied and Industrial Mathematics. - 2020. - 14. - № 2. - P. 308-320. - 10.1134/S199047892002009X