Solving 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 ?

EDIT : Here is a solution in C++

void SolveLinearSystem(u8 A[32][32], u8 B[32])
{
int N = 32;
for (int K = 0; K < N; ++K) 
{
    if( A[K][K] == 0 ) 
    {
        for(int i = K + 1; i<N ; ++i ) 
        { 
            if(A[i][K] != 0) 
            {
                for( int L = 0; L < N; ++L )
                {
                    int s = A[K][L];
                    A[K][L] = A[i][L];
                    A[i][L] = s;
                }
                int s = B[i];
                B[i] = B[K];
                B[K] = s;
                    break;
            }
        }
    }

    for( int I = 0; I<N; ++I)
    {
        if( I!=K )
        { 
            if( A[I][K] ) 
            { 
                int M = 0;
                for( M=K; M<N; ++M ) 
                { 
                    A[I][M] = A[I][M] ^ A[K][M]; 
                }
                B[I] = B[I] ^ B[K];
            }
        }
    }
}
}

Answer 1

If you are familiar with solving regular systems of equations, this is not a major step up. When using real numbers in a system of equations, you do elimination like this:

[a b; c d] -> [a b; 0 d-(b*c/a)] -> [a 0; 0 d-(b*c/a)] -> [1 0; 0 1]

Note: here I use MATLAB matrix notation for ease-of-entry.

The important realization to make is that all of these matrix operations (i.e. dividing, multiplying, adding, and subtracting) exist for any field, not just the real numbers. If you are unfamiliar with the term field, it just means a group of values which allow for multiplication, negation, inversion, addition, etc.

This takes us to solving systems of xor equations. You currently describe your systems as a bunch of 16-bit values xor'd together. However, the way I'd chose to represent it as a bunch of bits xor'd together, For instance, if your first equation was:

p[0] = a[1] ^ a[2]

I'd represent this as:

p[0][0] = a[1][0] ^ a[2][0]
p[0][1] = a[1][1] ^ a[2][1]
…

Where the second set of brackets denotes the bit offset in the 16-bit value. So, each of your little equations would be equivalent to 16 equations.

Single bit xor operations on booleans form a field. In this field, we make the "addition" operator equivalent to xor. We can define the addition and multiplication tables as follows:

1 + 0 = 0 + 1 = 1; 1 + 1 = 0 + 0 = 0
1 * 0 = 0 * 1 = 0 * 0 = 0; 1 * 1 = 1

Division is only possible by 1 (because you cannot divide by zero), and so the division operator leaves an element unchanged.

With this, you should be able to form a matrix for your system of xor equations. This matrix will consist entirely of 1's and 0's. Then use the gauss-jordan elimination algorithm (it's really not too hard to implement) just as you would for ordinary real numbers. This will allow you to invert the matrix and find the solution.

I was personally so intrigued by this question that I wrote up a small C++ matrix implementation that allows you to supply any field you like. This may be a good starting point, or you may even wish to use my code altogether! Here's the source code on Github: XorSystem. I specifically suggest looking at the invert() method on ANMatrix.

Answer 2

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.