1

Given XOR values of 3 indices how can we find the numbers? Like say if I have indices from 1 to 7, how can I find the numbers by given XOR values?

I have:

  1. $X_{1} \oplus X_{3} \oplus X_{5}=V_1$

  2. $X_{1} \oplus X_{3} \oplus X_{6}=V_2$

  3. $X_{1} \oplus X_{4} \oplus X_{6}=V_3$
  4. $X_{2} \oplus X_{4} \oplus X_{6}=V_4$
  5. $X_{2} \oplus X_{4} \oplus X_{7}=V_5$
  6. $X_{2} \oplus X_{5} \oplus X_{7}=V_6$
  7. $X_{3} \oplus X_{5} \oplus X_{7}=V_7$

How can I find any $X_{i}$ from the above data? Is there any pattern?

Eric Wofsey
  • 330,363
Sahil Silare
  • 355

4 Answers4

3

Build the matrix $A$ in which the entry $A_{i,j}$ is $1$ if in the $i$th equation there is $X_j$ appearing on the left hand side and $0$ otherwise.

The XOR system is equivalent to the following system of linear equations over the field $\mathbb F_2$: $$ \left( \begin{array}{ccccccc} 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{array} \right) \cdot \begin{pmatrix} X_1\\X_2\\X_3\\X_4\\X_5\\X_6\\X_7 \end{pmatrix} = \begin{pmatrix} V_1\\V_2\\V_3\\V_4\\V_5\\V_6\\V_7 \end{pmatrix} $$

The matrix on the left is the matrix $A$ that I made you build at the beginning.

The system is certainly solvable if the matrix $A$ is invertible in $\mathbb F_2$.

In our case, $\det(A)=-3$, so it is possible to solve the system.

This is the inverse matrix: $$ \left( \begin{array}{ccccccc} 1 & 1 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \end{array} \right) . $$ To compute $X_i$, read the $i$th row and look for the columns where $1$ is present. Those are the indices of your original equations that you have to XOR together. For instance, for $X_1$ you have to XOR together $$ X_1 = V_1 \oplus V_2 \oplus V_3 \oplus V_5 \oplus V_6 . $$

Federico
  • 5,900
  • Can you explain the first line more? – Sahil Silare Dec 10 '18 at 18:07
  • 1
    $X_1\oplus X_3\oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $\mathbb F_2 = \mathbb Z/(2\mathbb Z)$. Therefore your system of XOR equations is actually a linear system of equations in the field $\mathbb F_2$. The same theory of linear systems on $\mathbb R$ or $\mathbb C$ applies here. In particular, your system is solvable if the matrix has full rank. Here I compute the standard determinant and find out which is $-3$, which is not $0$ in $\mathbb F_2$, so the matrix is invertible – Federico Dec 10 '18 at 18:13
  • The first row is just telling you to build the usual matrix that you would build for a linear system of equations. You simply write $X_1+X_3+X_5 = (1,0,1,0,1,0,0) \cdot (X_1, X_2, X_3, X_4, X_5, X_6, X_7)$ – Federico Dec 10 '18 at 18:14
  • Please add the matrix A for better understanding! – Sahil Silare Dec 10 '18 at 18:14
  • @SahilSilare sorry i didn't have time before. I hope this helps you solve any other system that you might encounter. Just remember that solving XOR systems is like solving linear systems in $\mathbb F_2$ – Federico Dec 10 '18 at 18:20
  • What if I have 6 constraints? Then the solution doesn't exist? – Sahil Silare Dec 10 '18 at 18:21
  • Usual theory applies: you have the linear system $AX=V$ and you just need to solve that – Federico Dec 10 '18 at 18:23
  • Okay, then can you create a matrix with no column more than 3 ones and it should be 6x6 matrix – Sahil Silare Dec 10 '18 at 18:24
  • "can you create a matrix with no column more than 3 ones and it should be 6x6 matrix" What do you mean? Do you have another system to solve? – Federico Dec 10 '18 at 18:25
  • Thanks it's sorted now. – Sahil Silare Dec 10 '18 at 20:36
1

If we XOR lines 1 and 2, we get $$ X_5\oplus X_6 = V_1\oplus V_2 $$ XORing lines 4 and 5 gives us $$ X_6\oplus X_7 = V_4\oplus V_5 $$ XORing these two together, we get $$ X_5\oplus X_7 = V_1\oplus V_2\oplus V_4\oplus V_5 $$ Finally, XORing this with either line 6 or 7 gives us $X_2$ and $X_3$ respectively.

From this you should be able to squeeze out the remaining unknowns. Just be clever about which lines you XOR, and keep track of what you already know so that you can hope to eliminate those at every turn.

Arthur
  • 199,419
  • @Federico Sure. But if you don't apply "lucky algorithms" the times where you're lucky with your givens, and instead use the full machinery every time, then 1) that's boring, 2) when are you going to use the lucky algorithms? and 3) it's good to think for oneself from time to time. – Arthur Dec 10 '18 at 15:35
  • I agree, but I thought it would have been more instructive for the OP to learn the general scheme, as he didn't seem to be aware of the relation with linear systems over $\mathbb F_2$, and that completely trivializes the question – Federico Dec 10 '18 at 18:30
1

Guide:

Let me solve for $X_7$.

First, I will compute $$X_1 \oplus \ldots \oplus X_7 = V_1 \oplus \ldots \oplus V_7$$

Then I can compute

$$X_1 \oplus X_2 \oplus X_3 \oplus X_4 \oplus X_5 \oplus X_6 = V_1 \oplus V_4$$

by considering the first and the fourth.

Now, we can compute $X_7$ by summing these two equations.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
1

Take XOR of all equations. This tells you that

$$ X_{1} \oplus X_{2} \oplus \dots X_{7}=V_1 \oplus V_2 \oplus \dots V_7 .$$

Now, to find value of any particular $X_i$ take xor of two equations where all variables except $X_i$ appear and then xor with the xor of all seven.

For instance, (1)&(4) gives you $X_7$, (1)&(5) gives you $X_6$ and so on.

Alex Smart
  • 81
  • This game is only playable when the system is very simple as in this case. Check my answer for the general treatment of the problem. – Federico Dec 10 '18 at 15:14
  • "The general problem ( solving a set of equations Xi1⊕Xi2⊕Xi3=ai ) is NP-complete." How is that?! A system of XOR equations is just a linear system in $\mathbb F_2$. Look https://math.stackexchange.com/questions/169921/how-to-solve-system-of-linear-equations-of-xor-operation – Federico Dec 10 '18 at 15:32
  • You are of course right. Finding the maximum number of equations that can be satisfied is NP-hard but finding whether the equations can all be satisfied simultaneously is not. – Alex Smart Dec 10 '18 at 16:24