On local exponents of the mixing graphs for the functions realized by A5/1 type algorithms

S. N. Kyazhin ; V. M. Fomichev

Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 11-13

Résumé

It is shown that the mixing graphs for the functions realized by A5/1 type algorithms based on linear feedback shift registers of lengths $n,m,p$ with characteristic polynomials of weights $\nu,\mu,\pi$ are primitive. The following lower and upper bounds for the mixing graph exponent and local exponent depending on these parameters take place: $1+\max\{\lceil n/\nu\rceil,\lceil m/\mu\rceil,\lceil p/\pi\rceil\}\le\exp\Gamma\le\max\{n,m,p\}$. It is obtained that, for A5/1 algorithm, exponent $\exp\Gamma$ and local exponent $*J$-exp $\Gamma$, $J=\{1,20,42\}$, are equal to 21. This matches the idle running length of A5/1 generator.

Détail

Keywords: A5/1 generator, primitive graph, exponent, local exponent.