Finding numbers by given XOR values.

Question

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?

Answer 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.

Answer 2

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.

Answer 3

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.

Answer 4

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 . $$