You have a few variables that can only assume the values 0 or 1 and you use those to form two polynomials. Is there a way to multiply the two polynomials that is faster than O(n²) where n is the number of terms in the polynomial?
What I could come up with:
As the variables are binary, they all follow the equation X²=X
You can represent any polynomial of this kind with an array of $2^n$ values, where n is the number of variables, where each index represents the variables multiplied and the value at the index position represents the quantity multiplied.
Example: for a polynomial with 3 variables, the array indexes will be as follows:
0 - _
1 - a
2 - b
3 - a * b
4 - c
5 - a * c
6 - b * c
7 - a * b * c
And the polynomial 1+3a-2b+bc could be represented as [1, 3, -2, 0, 0, 0, 1, 0]
to add two polynomials in this representation you just have to add the arrays
the value of the multiplication of two terms can be calculated multiplying their values and the index can be found by applying OR in their indexes. Example: array A and array B represents two distinct binary polynomials and K is the result of the multiplication.
A[i] * B[j]->
K[i | j] = A[i] * B[j]
So, is there a faster way than looping and distributing each term?