# Reducing the XOR's in Implementation Cost

Suppose that we want to implement the following equations in binary finite field.

$$\begin{array}{l}\tag{1} y_{{1}}=x_{{1}}\oplus x_{{2}}\oplus x_{{7}}\oplus x_{{8}},\\ y_{{2}}=x_{{1}}\oplus x_{{2}}\oplus x_{{6}}\oplus x_{{8}},\\ y_{{3}}=x_{{1}}\oplus x_{{2}}\oplus x_{{7}},\\ y_{{4}}=x_{{2}}\oplus x_{{8}}. \end{array}$$

My question: Is it possible to implement the given equations in $$(1)$$ with five $$\operatorname{XOR}$$?

My try results in six $$\operatorname{XOR}$$ for implementation cost. For example;

$$\begin{array}{l}\tag{2} u_1=x_1\oplus x_2,\\ u_2=x_2\oplus x_8=y_4\\ u_3=x_6\oplus x_8,\\ u_4=u_1\oplus x_7=y_3\\ u_5=u_4\oplus x_8=y_1\\ u_6=u_1\oplus u_3=y_2\\ \end{array}$$

Thanks for any suggestions.

Edit: As Dear fgrieu said with greedy thoughts, the answer is as follows: $$\begin{array}{l}\tag{3} u_1=x_2\oplus x_8=y_4\\ u_2=x_1\oplus u_1\\ u_3=u_2\oplus x_7=y_1 \\ u_4=u_2\oplus x_6=y_2\\ u_5=u_3\oplus x_8=y_3 \end{array}$$

Thanks to greedy thoughts.

• This might better suits for CS? At the and this has graph based solutions? See MDS matrixes solved with A* algorithm. – kelalaka Jan 25 '19 at 13:13
• Instead of editing your question to include the answer, it would be better to post it as an answer of your own. – Ilmari Karonen Jan 25 '19 at 21:59

Yes. I have a solution with 5 $$\oplus$$.
Hint 1: That would not work with $$*$$ (ordinary multiplication, or even multiplication in $$\Bbb Z^*_p$$) where there is $$\oplus$$, because we must use a property of $$\oplus$$ that $$*$$ does not have.
Hint 3: It's key to compute $$y_3$$ late, with just one extra step.
• @Bissi: the one I know is exploring a tree of possibilities, with trimming when the current node can't lead to a solution because too many remain to be found (e.g. when we want $n=5$ operations at most, and need to produce $m=4$ different quantities not in the givens, it is obvious that we can afford only $n-m=1$ operation not leading to a quantity to be produced). Note: greedy is the common term for exploration strategies that explore first those branches leading to a partial desired result. In many but not all cases, that's optimum. – fgrieu Jan 25 '19 at 17:40