patternMinor
Is is possible to determine if a given number is xor combination of some numbers?
Viewed 0 times
combinationxornumbernumberspossiblesomedeterminegiven
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#111539, answer score: 4
Revisions (0)
No revisions yet.