On the decomposition of a vectorial boolean function into a composition of two functions

In the paper, we prove that if a vectorial Boolean function F in n variables, deg(F) = d > 2, is decomposable, then the function F' = A₂ о F о A₁, where A₁, A₂ are arbitrary affine (n, n)-permutations, is also decomposable; and if F(x) = G(H(x)), max{deg(F), deg(H)} = d' < d, function H is invertible and deg(H^-1) ^ d', then the function F = F + A₀ is decomposable for any affine function A₀. The construction of a decomposable vectorial Boolean function of the third degree in an arbitrary number of variables is presented. A computational experiment showed that all vectorial Boolean functions of the third degree in three variables are decomposable.

Keywords

Authors

References