# Counting the $\operatorname{XOR}$ of an Element over the Finite Field $\operatorname{GF}(2^q)$

Definition: The $\operatorname{XOR}$ count of an element $\alpha$ in the finite field $\operatorname{GF}(2^q)$ is the number of $\operatorname{XOR}s$ required to implement the multiplication of $\alpha$ with an arbitrary $\beta$ over $\operatorname{GF}(2^q)$.

Example: Consider we want to compute the $\operatorname{XOR}$ count of $\alpha=x +1$ over $\operatorname{GF}(2^4)$ with the irreducible polynomial ${\bf f}=x^4+x+1$. We denote the element $\alpha$ with $(0,0,1,1)$. Let $(b_3, b_2, b_1, b_0)$ be the binary representation of an arbitrary element $\beta$ in the field $\operatorname{GF}(2^4)$, then we obtain

$$\begin{array}{rcl} (0, 0, 1, 1) · (b_3, b_2, b_1, b_0) &=& (b_2, b_1, b_0 ⊕ b_3, b_3) ⊕ (b_3, b_2, b_1, b_0)\\ \\ &=& (b_2 ⊕ b_3, b_1 ⊕ b_2, b_0 ⊕ b_1 ⊕ b_3, b_0 ⊕ b_3), \end{array}$$ which corresponds to $5$ $\operatorname{XOR}$s.

Note: The $\operatorname{XOR}$ counting problem is depending on the irreducible polynomial of the field.

For instance, consider $\operatorname{GF}(2^4)$ with the irreducible polynomial ${\bf f}=x^4+x^3+1$, then we get

$$\begin{array}{rcl} (0, 0, 1, 1) · (b_3, b_2, b_1, b_0) &=& (b_2 ⊕ b_3, b_1, b_0, b_3) ⊕ (b_3, b_2, b_1, b_0)\\ \\ &=& (b_2, b_1 ⊕ b_2, b_0 ⊕ b_1, b_0 ⊕ b_3), \end{array}$$ which corresponds to $3$ $\operatorname{XOR}$s.

My question: Is there an algorithm or a software such that its input be a finite field $\operatorname{GF}(2^q)$ and an element $\alpha$ of $\operatorname{GF}(2^q)$ and its output be the $\operatorname{XOR}$ of $\alpha$ over $\operatorname{GF}(2^q)$.

Thanks for any suggestions.

• "$(b_2 \oplus b_3, b_1 \oplus b_2, b_0 \oplus b_1 \oplus b_3, b_0 \oplus b_3)$ which corresponds to 5 $XOR$s", actually, that can be computed with 4 xor's (you compute $t = b_0 \oplus b_3$, and then output $(b_2 \oplus b_3, b_1 \oplus b_2, t \oplus b_1, t)$ – poncho Mar 30 '18 at 17:26
• So, how is XOR count defined then? If it's not literally "the minimal number of XORs required", then what is it? – poncho Mar 30 '18 at 17:31
• The word "required" implies minimal; if the XOR count was 5, that would mean that 5 XORs would be required, that is, there was no way to compute it with only 4. Hence, if you are asking for an algorithm to compute an XOR count, you need to define what it is (and if you want the answer to the first instance to be 5, you need to define it accordingly) – poncho Mar 30 '18 at 17:50
• What does "its output be the $\operatorname{XOR}$ of $\alpha$ over $\operatorname{GF}(2^q)$ mean? XOR of $\alpha$ with what? You can't have an XOR of just one element: XOR is a two-input-one-output operation. – Dilip Sarwate Mar 30 '18 at 21:25
• @DilipSarwate Thank you so much for your comment Professor Sarwate. I make an example to clarify what I mean by"input" and "output" . Consider $\operatorname{GF}(2^8)$ with irreducible polynomial ${\bf f}=x^8+x^4+x^3+x+1$. The algorithm inputs $\operatorname{GF}(2^8)$ and an element of this field such as $\alpha=x+1$ and then computes the number of $\operatorname{XOR}s$ required to implement the multiplication of $\alpha$ with an arbitrary $\beta$ over $\operatorname{GF}(2^8)$. For this example, it can be checked that the output is $11$(Tables 6-13). – Amin235 Mar 31 '18 at 10:59

Let $f=x^q+t$ be an irreducible polynomial, then
$$\alpha\cdot \beta= (\alpha_{q-1},\dots,\alpha_0)\cdot(\beta_{q-1},\dots,\beta_0): \bigoplus_{i=0,\alpha_i\neq0}^{q-1}\big( \alpha_i\cdot(\beta<<i) \oplus (\bigoplus_{j=1}^{i} \beta_{q-j}\cdot x^{j-1}\cdot t)\big).$$
With this formula, you can easily calculate XOR count of $\alpha$. Although there may be a simpler solution to answer your question. Note that in this formula, several $\beta_ k$ may be xor with each other, which should not be taken into account in the XOR count calculation. For this, a $q\times q$ matrix can be used for implementation.
Edit: As an example, let $f=x^8+x^4+x^3+x+1=x^8+t$. Then $$(x+1)\cdot \beta=\alpha_0\cdot (\beta_7,\dots,\beta_0)\oplus \alpha_1\cdot (\beta_6,\dots,\beta_0,0)\oplus \beta_7 \cdot t=(\beta_7,\dots,\beta_0)\oplus (\beta_6,\dots,\beta_0,0)\oplus (0,0,0,\beta_7,\beta_7,0,\beta_7,\beta_7)=(\beta_7\oplus \beta_6,\beta_6\oplus \beta_5,\beta_5\oplus \beta_4,\beta_4\oplus \beta_3\oplus \beta_7,\beta_3\oplus \beta_2\oplus \beta_7,\beta_2\oplus \beta_1,\beta_1\oplus \beta_0\oplus \beta_7,\beta_0\oplus \beta_7).$$ So, the XOR count of $x+1$ is $11$.
• Thanks for your answer Meysam. Is it possible to ask you by applying your formula to obtain $\operatorname{XOR}$ of the example of my last comment. – Amin235 Mar 31 '18 at 14:44