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.

  • $\begingroup$ This might better suits for CS? At the and this has graph based solutions? See MDS matrixes solved with A* algorithm. $\endgroup$
    – kelalaka
    Jan 25 '19 at 13:13
  • 1
    $\begingroup$ Instead of editing your question to include the answer, it would be better to post it as an answer of your own. $\endgroup$ 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 2: The right path is greedy.

Hint 3: It's key to compute $y_3$ late, with just one extra step.

  • $\begingroup$ @fgrieu Is there an algorithm for this kind of problem ? $\endgroup$
    – Bissi
    Jan 25 '19 at 15:48
  • 2
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Jan 25 '19 at 17:40

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.