Finding numbers by given XOR values.












1












$begingroup$


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?










share|cite|improve this question











$endgroup$

















    1












    $begingroup$


    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?










    share|cite|improve this question











    $endgroup$















      1












      1








      1


      1



      $begingroup$


      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?










      share|cite|improve this question











      $endgroup$




      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?







      binary bit-strings






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Jan 11 at 5:55









      Eric Wofsey

      185k14213340




      185k14213340










      asked Dec 10 '18 at 14:31









      Sahil SilareSahil Silare

      11619




      11619






















          4 Answers
          4






          active

          oldest

          votes


















          1












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Can you provide more info if the index is 6 instead of 7?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 14:50










          • $begingroup$
            For $x_6$, you can sum up the first and the fifth. If you are looking for $x_6$, look for two equations without that variable and also the sum of the equations should cover the other variables.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 14:55










          • $begingroup$
            No, I mean like if I have indices 1 to 6 then how can I compute individual values by constructing equations?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 15:52










          • $begingroup$
            hmm... i don't quite understand your question.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 15:59










          • $begingroup$
            Let say I have $X_{1},X_{2},X_{3}cdots X_{6}$ then how can I find values by finding any 3 number's XOR values?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 16:00





















          3












          $begingroup$

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






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Can you explain the first line more?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:07






          • 1




            $begingroup$
            $X_1oplus X_3oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $mathbb F_2 = mathbb Z/(2mathbb 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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:13










          • $begingroup$
            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)$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:14












          • $begingroup$
            Please add the matrix A for better understanding!
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:14










          • $begingroup$
            @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$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:20



















          1












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            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.
            $endgroup$
            – Federico
            Dec 10 '18 at 15:14










          • $begingroup$
            "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 math.stackexchange.com/questions/169921/…
            $endgroup$
            – Federico
            Dec 10 '18 at 15:32










          • $begingroup$
            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.
            $endgroup$
            – Alex Smart
            Dec 10 '18 at 16:24



















          1












          $begingroup$

          If we XOR lines 1 and 2, we get
          $$
          X_5oplus X_6 = V_1oplus V_2
          $$

          XORing lines 4 and 5 gives us
          $$
          X_6oplus X_7 = V_4oplus V_5
          $$

          XORing these two together, we get
          $$
          X_5oplus X_7 = V_1oplus V_2oplus V_4oplus 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.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            @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.
            $endgroup$
            – Arthur
            Dec 10 '18 at 15:35










          • $begingroup$
            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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:30













          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033987%2ffinding-numbers-by-given-xor-values%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          4 Answers
          4






          active

          oldest

          votes








          4 Answers
          4






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          1












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Can you provide more info if the index is 6 instead of 7?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 14:50










          • $begingroup$
            For $x_6$, you can sum up the first and the fifth. If you are looking for $x_6$, look for two equations without that variable and also the sum of the equations should cover the other variables.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 14:55










          • $begingroup$
            No, I mean like if I have indices 1 to 6 then how can I compute individual values by constructing equations?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 15:52










          • $begingroup$
            hmm... i don't quite understand your question.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 15:59










          • $begingroup$
            Let say I have $X_{1},X_{2},X_{3}cdots X_{6}$ then how can I find values by finding any 3 number's XOR values?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 16:00


















          1












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Can you provide more info if the index is 6 instead of 7?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 14:50










          • $begingroup$
            For $x_6$, you can sum up the first and the fifth. If you are looking for $x_6$, look for two equations without that variable and also the sum of the equations should cover the other variables.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 14:55










          • $begingroup$
            No, I mean like if I have indices 1 to 6 then how can I compute individual values by constructing equations?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 15:52










          • $begingroup$
            hmm... i don't quite understand your question.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 15:59










          • $begingroup$
            Let say I have $X_{1},X_{2},X_{3}cdots X_{6}$ then how can I find values by finding any 3 number's XOR values?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 16:00
















          1












          1








          1





          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$



          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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Dec 10 '18 at 14:44









          Siong Thye GohSiong Thye Goh

          101k1466118




          101k1466118












          • $begingroup$
            Can you provide more info if the index is 6 instead of 7?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 14:50










          • $begingroup$
            For $x_6$, you can sum up the first and the fifth. If you are looking for $x_6$, look for two equations without that variable and also the sum of the equations should cover the other variables.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 14:55










          • $begingroup$
            No, I mean like if I have indices 1 to 6 then how can I compute individual values by constructing equations?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 15:52










          • $begingroup$
            hmm... i don't quite understand your question.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 15:59










          • $begingroup$
            Let say I have $X_{1},X_{2},X_{3}cdots X_{6}$ then how can I find values by finding any 3 number's XOR values?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 16:00




















          • $begingroup$
            Can you provide more info if the index is 6 instead of 7?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 14:50










          • $begingroup$
            For $x_6$, you can sum up the first and the fifth. If you are looking for $x_6$, look for two equations without that variable and also the sum of the equations should cover the other variables.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 14:55










          • $begingroup$
            No, I mean like if I have indices 1 to 6 then how can I compute individual values by constructing equations?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 15:52










          • $begingroup$
            hmm... i don't quite understand your question.
            $endgroup$
            – Siong Thye Goh
            Dec 10 '18 at 15:59










          • $begingroup$
            Let say I have $X_{1},X_{2},X_{3}cdots X_{6}$ then how can I find values by finding any 3 number's XOR values?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 16:00


















          $begingroup$
          Can you provide more info if the index is 6 instead of 7?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 14:50




          $begingroup$
          Can you provide more info if the index is 6 instead of 7?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 14:50












          $begingroup$
          For $x_6$, you can sum up the first and the fifth. If you are looking for $x_6$, look for two equations without that variable and also the sum of the equations should cover the other variables.
          $endgroup$
          – Siong Thye Goh
          Dec 10 '18 at 14:55




          $begingroup$
          For $x_6$, you can sum up the first and the fifth. If you are looking for $x_6$, look for two equations without that variable and also the sum of the equations should cover the other variables.
          $endgroup$
          – Siong Thye Goh
          Dec 10 '18 at 14:55












          $begingroup$
          No, I mean like if I have indices 1 to 6 then how can I compute individual values by constructing equations?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 15:52




          $begingroup$
          No, I mean like if I have indices 1 to 6 then how can I compute individual values by constructing equations?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 15:52












          $begingroup$
          hmm... i don't quite understand your question.
          $endgroup$
          – Siong Thye Goh
          Dec 10 '18 at 15:59




          $begingroup$
          hmm... i don't quite understand your question.
          $endgroup$
          – Siong Thye Goh
          Dec 10 '18 at 15:59












          $begingroup$
          Let say I have $X_{1},X_{2},X_{3}cdots X_{6}$ then how can I find values by finding any 3 number's XOR values?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 16:00






          $begingroup$
          Let say I have $X_{1},X_{2},X_{3}cdots X_{6}$ then how can I find values by finding any 3 number's XOR values?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 16:00













          3












          $begingroup$

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






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Can you explain the first line more?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:07






          • 1




            $begingroup$
            $X_1oplus X_3oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $mathbb F_2 = mathbb Z/(2mathbb 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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:13










          • $begingroup$
            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)$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:14












          • $begingroup$
            Please add the matrix A for better understanding!
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:14










          • $begingroup$
            @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$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:20
















          3












          $begingroup$

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






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Can you explain the first line more?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:07






          • 1




            $begingroup$
            $X_1oplus X_3oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $mathbb F_2 = mathbb Z/(2mathbb 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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:13










          • $begingroup$
            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)$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:14












          • $begingroup$
            Please add the matrix A for better understanding!
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:14










          • $begingroup$
            @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$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:20














          3












          3








          3





          $begingroup$

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






          share|cite|improve this answer











          $endgroup$



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







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 10 '18 at 18:19

























          answered Dec 10 '18 at 14:54









          FedericoFederico

          5,034514




          5,034514












          • $begingroup$
            Can you explain the first line more?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:07






          • 1




            $begingroup$
            $X_1oplus X_3oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $mathbb F_2 = mathbb Z/(2mathbb 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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:13










          • $begingroup$
            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)$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:14












          • $begingroup$
            Please add the matrix A for better understanding!
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:14










          • $begingroup$
            @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$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:20


















          • $begingroup$
            Can you explain the first line more?
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:07






          • 1




            $begingroup$
            $X_1oplus X_3oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $mathbb F_2 = mathbb Z/(2mathbb 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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:13










          • $begingroup$
            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)$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:14












          • $begingroup$
            Please add the matrix A for better understanding!
            $endgroup$
            – Sahil Silare
            Dec 10 '18 at 18:14










          • $begingroup$
            @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$
            $endgroup$
            – Federico
            Dec 10 '18 at 18:20
















          $begingroup$
          Can you explain the first line more?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 18:07




          $begingroup$
          Can you explain the first line more?
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 18:07




          1




          1




          $begingroup$
          $X_1oplus X_3oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $mathbb F_2 = mathbb Z/(2mathbb 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
          $endgroup$
          – Federico
          Dec 10 '18 at 18:13




          $begingroup$
          $X_1oplus X_3oplus X_5$ is nothing other than standard addition $X_1+X_3+X_5$ in the field $mathbb F_2 = mathbb Z/(2mathbb 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
          $endgroup$
          – Federico
          Dec 10 '18 at 18:13












          $begingroup$
          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)$
          $endgroup$
          – Federico
          Dec 10 '18 at 18:14






          $begingroup$
          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)$
          $endgroup$
          – Federico
          Dec 10 '18 at 18:14














          $begingroup$
          Please add the matrix A for better understanding!
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 18:14




          $begingroup$
          Please add the matrix A for better understanding!
          $endgroup$
          – Sahil Silare
          Dec 10 '18 at 18:14












          $begingroup$
          @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$
          $endgroup$
          – Federico
          Dec 10 '18 at 18:20




          $begingroup$
          @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$
          $endgroup$
          – Federico
          Dec 10 '18 at 18:20











          1












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            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.
            $endgroup$
            – Federico
            Dec 10 '18 at 15:14










          • $begingroup$
            "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 math.stackexchange.com/questions/169921/…
            $endgroup$
            – Federico
            Dec 10 '18 at 15:32










          • $begingroup$
            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.
            $endgroup$
            – Alex Smart
            Dec 10 '18 at 16:24
















          1












          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            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.
            $endgroup$
            – Federico
            Dec 10 '18 at 15:14










          • $begingroup$
            "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 math.stackexchange.com/questions/169921/…
            $endgroup$
            – Federico
            Dec 10 '18 at 15:32










          • $begingroup$
            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.
            $endgroup$
            – Alex Smart
            Dec 10 '18 at 16:24














          1












          1








          1





          $begingroup$

          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.






          share|cite|improve this answer









          $endgroup$



          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.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered Dec 10 '18 at 14:48









          Alex SmartAlex Smart

          614




          614












          • $begingroup$
            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.
            $endgroup$
            – Federico
            Dec 10 '18 at 15:14










          • $begingroup$
            "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 math.stackexchange.com/questions/169921/…
            $endgroup$
            – Federico
            Dec 10 '18 at 15:32










          • $begingroup$
            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.
            $endgroup$
            – Alex Smart
            Dec 10 '18 at 16:24


















          • $begingroup$
            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.
            $endgroup$
            – Federico
            Dec 10 '18 at 15:14










          • $begingroup$
            "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 math.stackexchange.com/questions/169921/…
            $endgroup$
            – Federico
            Dec 10 '18 at 15:32










          • $begingroup$
            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.
            $endgroup$
            – Alex Smart
            Dec 10 '18 at 16:24
















          $begingroup$
          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.
          $endgroup$
          – Federico
          Dec 10 '18 at 15:14




          $begingroup$
          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.
          $endgroup$
          – Federico
          Dec 10 '18 at 15:14












          $begingroup$
          "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 math.stackexchange.com/questions/169921/…
          $endgroup$
          – Federico
          Dec 10 '18 at 15:32




          $begingroup$
          "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 math.stackexchange.com/questions/169921/…
          $endgroup$
          – Federico
          Dec 10 '18 at 15:32












          $begingroup$
          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.
          $endgroup$
          – Alex Smart
          Dec 10 '18 at 16:24




          $begingroup$
          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.
          $endgroup$
          – Alex Smart
          Dec 10 '18 at 16:24











          1












          $begingroup$

          If we XOR lines 1 and 2, we get
          $$
          X_5oplus X_6 = V_1oplus V_2
          $$

          XORing lines 4 and 5 gives us
          $$
          X_6oplus X_7 = V_4oplus V_5
          $$

          XORing these two together, we get
          $$
          X_5oplus X_7 = V_1oplus V_2oplus V_4oplus 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.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            @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.
            $endgroup$
            – Arthur
            Dec 10 '18 at 15:35










          • $begingroup$
            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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:30


















          1












          $begingroup$

          If we XOR lines 1 and 2, we get
          $$
          X_5oplus X_6 = V_1oplus V_2
          $$

          XORing lines 4 and 5 gives us
          $$
          X_6oplus X_7 = V_4oplus V_5
          $$

          XORing these two together, we get
          $$
          X_5oplus X_7 = V_1oplus V_2oplus V_4oplus 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.






          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            @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.
            $endgroup$
            – Arthur
            Dec 10 '18 at 15:35










          • $begingroup$
            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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:30
















          1












          1








          1





          $begingroup$

          If we XOR lines 1 and 2, we get
          $$
          X_5oplus X_6 = V_1oplus V_2
          $$

          XORing lines 4 and 5 gives us
          $$
          X_6oplus X_7 = V_4oplus V_5
          $$

          XORing these two together, we get
          $$
          X_5oplus X_7 = V_1oplus V_2oplus V_4oplus 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.






          share|cite|improve this answer











          $endgroup$



          If we XOR lines 1 and 2, we get
          $$
          X_5oplus X_6 = V_1oplus V_2
          $$

          XORing lines 4 and 5 gives us
          $$
          X_6oplus X_7 = V_4oplus V_5
          $$

          XORing these two together, we get
          $$
          X_5oplus X_7 = V_1oplus V_2oplus V_4oplus 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.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Dec 10 '18 at 14:53

























          answered Dec 10 '18 at 14:37









          ArthurArthur

          114k7115197




          114k7115197












          • $begingroup$
            @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.
            $endgroup$
            – Arthur
            Dec 10 '18 at 15:35










          • $begingroup$
            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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:30




















          • $begingroup$
            @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.
            $endgroup$
            – Arthur
            Dec 10 '18 at 15:35










          • $begingroup$
            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
            $endgroup$
            – Federico
            Dec 10 '18 at 18:30


















          $begingroup$
          @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.
          $endgroup$
          – Arthur
          Dec 10 '18 at 15:35




          $begingroup$
          @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.
          $endgroup$
          – Arthur
          Dec 10 '18 at 15:35












          $begingroup$
          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
          $endgroup$
          – Federico
          Dec 10 '18 at 18:30






          $begingroup$
          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
          $endgroup$
          – Federico
          Dec 10 '18 at 18:30




















          draft saved

          draft discarded




















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033987%2ffinding-numbers-by-given-xor-values%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Probability when a professor distributes a quiz and homework assignment to a class of n students.

          Aardman Animations

          Are they similar matrix