RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2020 Issue 13, Pages 31–32 (Mi pdma488)

Discrete Functions

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

G. M. Pintus

Novosibirsk State University

Abstract: 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_2 \circ F \circ A_1 $, where $ A_1, A_2 $ 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}) \leq d'$, then the function $ F^{''} = F + A_0 $ is decomposable for any affine function $A_0$. 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: vectorial Boolean function, decomposition, threshold implementation.

UDC: 519.7

DOI: 10.17223/2226308X/13/8



© Steklov Math. Inst. of RAS, 2024