I am using polynomials to represent bit vectors, such that the value of the d-th coefficient is $1$ if the d-th bit in the vector is $1$, and $0$ otherwise. For example, the vector $A = [1, 1, 0, 1, 0]$ is represented by the polynomial $P_A(x) = 1 + 1x + 0x^2 + 1x^3 + 0x^4 = 1 + x + x^3$.

I understand that I can find the number of bits $1$ in the bitwise AND of two vectors, $|A \wedge B|$, by multiplying $P_A(x)$ and the "inverted" $P_B(x)$ and checking the (d-1)-th coefficient in the resulting polynomial, as explained in Scalar product of vectors over polynomial rings.

Now I want a similar way to find the number of bits $1$ in the bitwise OR: $|A \vee B|$. Considering $|A \vee B| = |A| + |B| - |A \wedge B|$, so far I thought about of $|A|$ by multiplying $P_A(x) \cdot P_1(x)$, where $P_1(x)$ is the polynomial having the value $1$ for all coefficients. Then, I would do the same to find $|B|$.

This would require three polynomial multiplications and two additions: $P_A(x) \cdot P_1(x) + P_B(x) \cdot P_1(x) + P_A(x) \cdot P_B(x)$. Since the first two have $P_1(x)$ in common, it is possible to simplify it a bit: $(P_A(x) + P_B(x)) \cdot P_1(x) + P_A(x) \cdot P_B(x)$, using a total of two polynomial multiplications.

My question is: Is there a way to do this using fewer polynomial multiplications?

  • $\begingroup$ What operators on polynomials can you use? If you can also use polynomial addition with a constant polynomial, there's a solution based on the technique you use for $|A \wedge B|$, with additionally two polynomial additions and an integer subtraction. $\endgroup$ – fgrieu Aug 19 '17 at 9:04
  • $\begingroup$ Additions and multiplications are available. And, since I'm basically using this for homomorphic encryption, I'd rather have more additions than multiplications. Could you give more details about this solution you mentioned? $\endgroup$ – mshcruz Aug 19 '17 at 10:15

It holds that $$\begin{align}|A \vee B|&=d-1-|\overline{A \vee B}|\\ &=d-1-|\overline A \wedge \overline B| \end{align}$$

Define $K(x)$ as the polynomial of degree $d-1$ with all 1 coefficients. $\overline A$ can be represented as the polynomial $K(x)-A(x)$.

Thus the desired $|A \vee B|$ is obtained by subtracting from $d-1$ the coefficient for $x^{d-1}$ of the polynomial $(K(x)-A(x))\cdot(K(x)-\tilde B(x))$, where $\tilde B(x)$ is $B(x)$ with "inversion" of coefficients, that is the coefficient of degree $i$ becomes coefficient of degree $d-1-i$.

We can use polynomial addition rather than subtraction: $d-1$ minus the coefficient for $x^{d-1}$ of the polynomial $(A(x)+L(x))\cdot(\tilde B(x)+L(x))$ also works (where $L(x)$ is the polynomial of degree $d-1$ with all $-1$ coefficients).

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.