3
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ It’s a linear algebra question. $\endgroup$ Commented Jul 6, 2019 at 5:14
  • $\begingroup$ How should I approach it? I am using properties of boolean operators $\endgroup$
    – foobar
    Commented Jul 6, 2019 at 6:27
  • $\begingroup$ Use your knowledge of linear algebra. $\endgroup$ Commented Jul 6, 2019 at 6:56
  • $\begingroup$ Can you please explain a little? :) $\endgroup$
    – foobar
    Commented Jul 6, 2019 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$ Commented Jul 6, 2019 at 7:12

1 Answer 1

4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.