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

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?

• It’s a linear algebra question. – Yuval Filmus Jul 6 '19 at 5:14
• How should I approach it? I am using properties of boolean operators – Gohma Jul 6 '19 at 6:27
• Use your knowledge of linear algebra. – Yuval Filmus Jul 6 '19 at 6:56
• Can you please explain a little? :) – Gohma Jul 6 '19 at 7:05
• Regard bitwise representation of the numbers as vectors over ring of integers modulo 2. Then XOR is a sum of such vectors. – 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.