HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is is possible to determine if a given number is xor combination of some numbers?

Submitted by: @import:stackexchange-cs··
0
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?

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.