Michela Ceria edited bits4.tex  about 6 years ago

Commit id: f1eb9c20329fecc3d3ee548496f62e8efc2f6dcc

deletions | additions      

       

$$f (x, y, z) = axyz + bxy + cxz + dzy + ex + f y + gz + h,$$  where $a,b,c,d,e,f,g,h$ are in $\Fb$.  \end{Definition}  So we have In the ANF of any $f:(\Fb)^3 \rightarrow \Fb$ there are at most:  \begin{itemize}  \item 1 monomial of degree 3 $\rightarrow a \cdot xyz$ a\,xyz;$  \item 3 monomials of degree 2 $\rightarrow b \cdot xy; c \cdot xz; d \cdot   zy;$ b\,xy,\quad c\,xz,\quad d\,zy;$  \item 3 monomials of degree 1 $\rightarrow ex; f y; gz;$ e\,x,\quad f\,y,\quad g\,z;$  \item 1 monomial of degree 0 $\rightarrow  h;$  \end{itemize}  where the coefficients $a, b,... , h \in \Fb$ are bits. a monomial appears if and only if its corresponding coefficient is nonzero.  \\  \medskip  We want to  Let $B_3=\{f:(\Fb)^3 \rightarrow \Fb\}$.  Note that we have 8 coefficients $a, b, c, d, e, f, g, h \in \Fb$ and two   choices for each coefficient, so we have at most  $2^8$ functions in $B_3$ with ANF.  We need also the fact that if $f, g \in \Fb[x]$ in ANF