Binary Polynomials

Each mapping $f$ of the set \{0,1\}^n of $n$-dimensional binary vectors to $\{0,1\}$ is called Boolean function of $n$ variables and denoted by f(x_n,x_{n-1},...,x_1). For cryptography some properties of the Boolean functions are interesting. Let denote by B(n,k) the set of $n$-dimensional binary vectors that have $k$ $1$'s. The task is for given Boolean function $f$ to find the number of vectors (b_n,b_{n-1},...,b_1) from B(n,k) such that f(b_n,b_{n-1},...,b_1)=1.

The Boolean function will be given by its (unique) polynomial modulo $2$. In these polynomials the operations addition and multiplication modulo $2$ are used, defined as shown in the tables of Fig. 1. In the polynomial of a function any product of $m$ variables x_{i1} x_{i2} ... x_{im} could participate or not participate. So the general form of the polynomial for $n$ variables is:

where all coefficients a_j, j=0,1,...,N=2^n-1, are $0$'s or $1$'s and if the coefficient is equal to $0$ we will omit the corresponding product and if it is equal to $1$ we just will omit the coefficient. For example, the polynomial of the Boolean function disjunction of $2$ variables given on Fig. 2 is 0+1 \cdot x_1+1 \cdot x_2+1 \cdot x_2x_1=x_1+x_2+x_2x_1.