# How to solve a xor equation?

I have the following equations I need to solve for A and B:

       2A ⊕ B = 7
A ⊕ B = 14


Note:
All variables are unsigned 32-bit integers
⊕ is the XOR operator for 32-bit integers.

• $A=7, B=9$. Not known if answer is unique, though. – Zhuoran He Oct 24 '17 at 5:13
• It's not unique at all. Take any integer of the form $m\cdot 2^4$ and add it to both of them, and the xor is unchanged. – Arthur Oct 24 '17 at 5:27
• Hey, thanks for the answer,but what method do you use? – Berkane Brahim Oct 24 '17 at 5:46

## 1 Answer

XOR is the same as addition in the finite field $F_2$. Thus if we assume a solution exists with $A<8$ and $B<16$ (reasonable given the magnitudes of the right-hand sides) you can rewrite your equations as \begin{align*} \left[\begin{array}{cccc}0 & 1 & 0 & 0\\0 & 0& 1 & 0\\0 & 0& 0& 1\\0 & 0& 0&0\end{array}\right]\mathbf{A} + I_{4\times 4}\mathbf{B} &\equiv \left[\begin{array}{c}0\\1\\1\\1\end{array}\right]\\ I_{4\times 4}\mathbf{A} + I_{4\times 4}\mathbf{B}&\equiv\left[\begin{array}{c}1\\1\\1\\0\end{array}\right] \end{align*} in $F_2$, with the vector $\mathbf{A}$ containing the bits of $A$ (from most to least significant).

We thus have an $8\times 8$ linear system over $F_2$, which you can row-reduce to get $$\left[\begin{array}{cccccccc}1 & 0 &0 &0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 &0 &0 &1 & 1 & 0 &0\\ 0 & 0 &0 &0 &0 & 1 & 1 &0\\ 0 & 0 &0 &0 &0 & 0 & 1 &1\\ 0 & 0 &0 &0 &0 &0 &0 &1 \end{array}\right]\left[\begin{array}{c}\mathbf{A}\\\mathbf{B}\end{array}\right] \equiv \left[\begin{array}{c}1\\1\\1\\0\\0\\1\\0\\1\\1\end{array}\right]$$ and finally back-substitute to get $$\mathbf{A} = \left[\begin{array}{c}0\\1\\1\\1\end{array}\right], \mathbf{B}=\left[\begin{array}{c}1\\0\\0\\1\end{array}\right].$$

But wait, as pointed out in the comments, the answer isn't unique... that's right, notice that at the beginning we assumed that both $A$ and $B$ had at most 4 bits, and that $A<8$. If we allow larger $A$ or $B$ we get larger linear systems (which will be rank-deficient).

• how about 32 bits? – Berkane Brahim Oct 24 '17 at 21:09
• @BerkaneBrahim Sure? Just set up the exact same type of linear system (it will be 64 x 64). – user7530 Oct 24 '17 at 22:47