# Thread: How to reduce algebraic degree of Boolean Functions?

1. ## How to reduce algebraic degree of Boolean Functions?

Hi everybody,

I would much appreciate if anyone could assist me with the following problem:

Given:
consider a 4-bit input vector
$\displaystyle x=(a,b,c,d)$, with $\displaystyle a,b,c,d \in GF(2)$.

Now consider a function
$\displaystyle S(x) = (S_3(x),S_2(x),S_1(x),S_0(x))$, with $\displaystyle S:GF(2)^4 \rightarrow GF(2)^4$ and $\displaystyle S_3,S_2,S_1,S_0:GF(2)^4 \rightarrow GF(2)$,
i.e. the component functions $\displaystyle S_3,S_2,S_1,S_0$ are Boolean functions of algebraic degree $\displaystyle \leq 3$.

Now consider two functions $\displaystyle Z,Y: GF(2)^4 \rightarrow GF(2)^4$ that have the following properties:
$\displaystyle Y(x)=(e(x),f(x),g(x),h(x))=y$
$\displaystyle Z(y)=(i(y),j(y),k(y),l(y))=z$
with the component functions
$\displaystyle e,f,g,h,i,j,k,l:GF(2)^4 \rightarrow GF(2)$ also being Boolean functions but only with an algebraic degree $\displaystyle \leq 2$.
$\displaystyle y,z \in GF(2)^4$ denote the two 4-bit output vectors of $\displaystyle Y$ and $\displaystyle Z$.

Wanted:
I am looking for Boolean functions $\displaystyle e,f,g,h,i,j,k,l$ with algebraic degree $\displaystyle \leq 2$, such that
$\displaystyle S(x) = Z(y) = Z(Y(x))$ holds.

I have already looked at Matlab, but it seems that it does not supports Boolean algebra

Does anyone has any idea how to approach this problem?

Thanks!