How to solve systems of XOR equations?

Question

I have to solve a system that consists of 32 xor equations, each involving 15 of 32 variables. One would look like this:

i[0] = p[0] ^ p[4] ^ p[5] ^ p[10] ^ p[11] ^ p[20] ^ p[21] ^ p[22] ^ p[23] ^ p[25] ^ p[26] ^ p[27] ^ p[28] ^ p[30] ^ p[31]

i[n] and p[n] being 16 bit integers.

So as I understand I would end up with a 32x32 matrix (containing only 1s and 0s) and a 32 result vector.

Apparently Gaussian elimination is what I need but I can't wrap my mind around the problem, could someone give me some insight on how to solve such a problem?

Answer 1

Yes, you can use gaussian elimination to solve this. The key is to recognize that the XOR operation is equivalent to addition modulo 2. So the equation you wrote is equivalent to

i[0] = (p[0] + p[4] + ... ) mod 2

You can then set the whole system up as a matrix equation

M*p=i mod 2

You can solve this using Gaussian elimination as usual, except that all of your operations will be performed modulo 2. Since your matrix contains a lot of 0s, then you are going to have to use pivoting, but other than that, the algorithm is the same.