Построение биективных отображений на основе линейного регистра сдвига и нелинейной функции выхода

Промышленные АСУ и контроллеры. 2014. № 4. С. 34–39.

Rozhkov M.

The paper deals with the methods of construction of bijective mappings Вf,L(x)=(f(x),f(d(x)),…,f(dn-1(x)), xÎ(F2)n, the coordinate functions of which are set by the great length shift register with the function of feedback L=L(x1,x2,…,xn)  and a removal nonlinear function f=f(x1,x2,...,xk) of a small number of arguments k (k<<n). It is known, the  orthogonality of the coordinate functions (f(x),f(d(x)),...,f(dn-1(x)) is equivalent to the mapping Вf,L is bijective. The article develops  the method, which reduce the original problem to the verification of orthogonal systems of Boolean functions with shift registers of limited length n<n0, that allows efficient use of its computing solutions.This method, in particular, allowed to build new infinite classes of bijective mappings Вf,L for the case of nonlinear function f, depending on five variables f=f(x1,x2,x3,x4,x5). Earlier, similar results were known for the case when the function f depends on three and four arguments. The results can be useful for construction and proof of the statistical properties of the random sequences generating on the basis of filter generators. The choice of pairs (f,L), in which simultaneously the mapping Bf,L is  bijective and period of dL is maximal has the particular practical importance.

Keywords: ортогональные системы функций, регистр сдвига, orthogonal system of Boolean functions, feedback shift register, filter generator, restrictive multitude, фильтрующий генератор, понижающие множества