I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$d$,$e$)

e.g - ($a$ xor $d$) , ($b$ xor $c$ xor $e$) , ( $a$ xor $e$ )

What i know clearly is that lets say X= ($b$ xor $d$) , Now if I xor X and Y i get ($a$ xor $c$ xor $e$), as ( $b$ xor $b$=0 ) and if it was some number not a xor combination (say $p$ ) then i would have got ($a$ xor $b$ xor $c$ xor $d$ xor $e$ xor $p$)

How should i approach this question?

  • $\begingroup$ It’s a linear algebra question. $\endgroup$ – Yuval Filmus Jul 6 '19 at 5:14
  • $\begingroup$ How should I approach it? I am using properties of boolean operators $\endgroup$ – foobar Jul 6 '19 at 6:27
  • $\begingroup$ Use your knowledge of linear algebra. $\endgroup$ – Yuval Filmus Jul 6 '19 at 6:56
  • $\begingroup$ Can you please explain a little? :) $\endgroup$ – foobar Jul 6 '19 at 7:05
  • $\begingroup$ Regard bitwise representation of the numbers as vectors over ring of integers modulo 2. Then XOR is a sum of such vectors. $\endgroup$ – Dmitri Urbanowicz Jul 6 '19 at 7:12

Suppose that your numbers are $n$-bit long. Then you can think of them as elements of the vector space $\mathbb{F}_2^n$. The number $X$ can be written as an XOR of $a_1,\ldots,a_m$ if $X$ is in the linear span of $a_1,\ldots,a_m$. In order to determine whether $X$ is in the linear span of $a_1,\ldots,a_m$, you can use Gaussian elimination.


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.