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.

  • $\begingroup$ "Better" is vague and a matter of opinion. Can you be more precise about your criteria for what counts as better and how you will evaluate proposed answers? I imagine there are likely multiple possible representations with different tradeoffs; as you haven't given us any information about how you want to select among those tradeoffs, it is not possible to select which of those are best. For instance, do you expect to deal mostly with sparse polynomials? Do you want to optimize for speed of one operation over another? etc. $\endgroup$
    – D.W.
    Commented Nov 21, 2021 at 3:10
  • $\begingroup$ en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/Kronecker_substitution $\endgroup$
    – D.W.
    Commented Nov 21, 2021 at 3:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.