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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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