Bijective mappings generated by filtering generator

M. I. Rozhkov

Prikladnaâ diskretnaâ matematika, no. 1 (2014), pp. 27-39

Résumé

The paper deals with the methods for constructing bijective mappings $ B_{f,L}$ whose coordinate functions are defined by a great length shift register with a feedback function $L(x_1,x_2,\ldots,x_n)$ and with an output (filtering) nonlinear function $f(x_1,x_2,\ldots,x_k)$ depending on a small number $k$ of its arguments $(k\ll n).$ It is known that the orthogonality of the coordinate functions is equivalent to the bijectiveness of the mapping $B_{f,L}$. A method developed in the paper reduces the problem of bijectiveness of $B_{f,L}$ for any $n$ to the case of bounded $n$. The method allows to build new infinite classes of bijective mappings $B_{f,L}$ for nonlinear functions $f$ depending on four, five or six variables. Earlier, similar results were known for a function $f$ depending on three arguments. The results can be useful for constructing and proving statistical properties of random sequences generated on the basis of filter generators.

Détail

Keywords: orthogonal system of Boolean functions, feedback shift register, filter generator.