Massimiliano Sala edited bits4.tex  about 6 years ago

Commit id: e1caca9df5b5f457e72577ddd26044cedac50378

deletions | additions      

       

(we do not prove this last claim, leaving it as a useful exercise to the reader).   \\ Now, pointing out that the size of $B_3$ is $\vert B_3 \vert =   \vert(\Fb )^3 \vert = 2^8$, so there are as many functions in $B_3$ as the number of  possible ANFs, ANF's,  we get that $$\{f:(\Fb)^3 \rightarrow \Fb \textrm{ with ANF}\} = B_3,$$ \; =\; B_3 \,,$$  hence every function from $(\Fb)^3$ to $\Fb$ can be written in Absolute Normal Form.  %  \begin{Example}  Consider the function $f:(\Fb)^3 \rightarrow \Fb$  defined by \\ 

$f (x, y, z) = x + y$  \end{Example}  The following function, often used in cryptography, is called the  \emph{majority function}: $$f: (\Fb)^3 \rightarrow \Fb $$  $$(x,y,z)\mapsto xy+xz+yz.$$  This function returns value $1$ if and only if the majority among the input bits $x$, $y$ and $z$ holds value $1$ and $0$ otherwise i.e. if and only if the majority among the input bits $x$, $y$ and $z$ holds value $0$.