A Boolean polynomial in $n$ variables $x_1, \dots, x_n$ is an expression of the form $$\sum_{\mathbf{s} \in \{0,1\}^n} c_{\mathbf{s}} x_1^{s_1} \cdots x_n^{s_n}, \quad \text{ where } c_s \in \{0,1\} .$$ Addition of Boolean polynomials is performed modulo $2$, while multiplication follows the distributive property and the rule $x_i^2 = x_i$. Mathematically speaking, Boolean polynomials are the elements of the quotient ring $$\mathbb{F}_2[x_1, \dots, x_n] / (x_1^2 - x_1, \dots, x_n^2 - x_n).$$ Note that there are $2^{2^n}$ Boolean polynomials in $n$ variables.
I'd like to write a fast implementation of addition and multiplication of Boolean polynomials in $n$ variables, when $n$ is small and fixed (say $n=5$ or $n=6$).
My first try is to store the coefficients of each Boolean polynomial as bits of an $n$-bits word. For the sake of explanation, let's assume $n = 3$. Then I store each Boolean polynomial $P$ as the $8$-bits word $$W_P = c_{000} | c_{001} | c_{010} | c_{011} | c_{100} | c_{101} | c_{110} | c_{111} .$$ With this representation, the addition of two Boolean polynomials $P$ and $Q$ is just a bit-wise xor. Using C notation: $$W_{P + Q} = W_P \wedge W_Q .$$ My issue is with multiplication. I can write multiplication by a single variable using shifts, ands, and xors: $$W_{Px_1} = (W_P \gg 4) \wedge W_P,$$ $$W_{Px_2} = ((W_P \,\&\, 11001100) \gg 2) \wedge W_P,$$ $$W_{Px_3} = ((W_P \,\&\, 10101010) \gg 1) \wedge W_P.$$ However, doing multiplication of two polynomials this way is not so efficient.
Does somebody know a better method? That is, involving a smallest number of bit-wise operations. Note that I'm more concerned about speed than memory, thus I'm fine with using more than $2^n$ bits to store a polynomial. Also, I'm assuming that the involved Boolean polynomials are completely random and not, for example, in any way sparse or structured.
