How to implement a Gaussian exception for binary equations

Question

I have this system of equations
1 = x⊕y⊕z
1 = x⊕y⊕w
0 = x⊕w⊕z
1 = w⊕y⊕z

I am trying to implement a Gaussian exception to solve this system as described here , replacing division, subtraction and multiplication with XOR, but it gives my wrong answer. The correct answer is: (x, y, z, w) = (0,1,0,0), what am I doing wrong?

public static void ComputeCoefficents(byte[,] X, byte[] Y) { int I, J, K, K1, N; N = Y.Length; for (K = 0; K < N; K++) { K1 = K + 1; for (I = K; I < N; I++) { if (X[I, K] != 0) { for (J = K1; J < N; J++) { X[I, J] /= X[I, K]; } //Y[I] /= X[I, K]; Y[I] ^= X[I, K]; } } for (I = K1; I < N; I++) { if (X[I, K] != 0) { for (J = K1; J < N; J++) { X[I, J] ^= X[K, J]; } Y[I] ^= Y[K]; } } } for (I = N - 2; I >= 0; I--) { for (J = N - 1; J >= I + 1; J--) { //Y[I] -= AndOperation(X[I, J], Y[J]); Y[I] ^= (byte)(X[I, J]* Y[J]); } } } 

Answer 1

I think that you are trying to apply the Gaussian mod 2 fix option for this.

In general, you can make a Gaussian algorithm for eliminating k if your equations are of the form

 a_1 * x + b_1 * y + c_1 * z = d_1 a_2 * x + b_2 * y + c_2 * z = d_2 a_3 * x + b_3 * y + c_3 * z = d_3 a_4 * x + b_4 * y + c_4 * z = d_4 

And in Z2 * there is and and + is xor , so you can use Gauz elimination to solve equations of the form

 x (xor) y (xor) z = 1 x (xor) y (xor) w = 1 x (xor) z (xor) w = 0 y (xor) z (xor) w = 1 

Allows you to execute this equation using a Gausian elimination manually.

Corresponding Extended Matrix:

  1 1 1 0 | 1 1 1 0 1 | 1 1 0 1 1 | 0 0 1 1 1 | 1 1 1 1 0 | 1 0 0 1 1 | 0 (R2 = R2 + R1) 0 1 0 1 | 1 (R3 = R3 + R1) 0 1 1 1 | 1 1 1 1 0 | 1 0 1 1 1 | 1 (R2 = R4) 0 1 0 1 | 1 0 0 1 1 | 0 (R4 = R2) 1 0 0 1 | 0 (R1 = R1 + R2) 0 1 1 1 | 1 0 0 1 0 | 0 (R3 = R3 + R2) 0 0 1 1 | 0 1 0 0 1 | 0 0 1 0 1 | 1 (R2 = R2 + R3) 0 0 1 0 | 0 0 0 0 1 | 0 (R4 = R4 + R3) 1 0 0 0 | 0 (R1 = R1 + R4) 0 1 0 0 | 1 (R2 = R2 + R4) 0 0 1 0 | 0 0 0 0 1 | 0 

Providing your solution (x, y, z, w) = (0,1,0,0).

But this requires a line break, which I do not see in your code.

There are several multiplications and divisions in your code that probably shouldn't be there. I expect the code to look like this: (you will need to fix TODO).

 public static void ComputeCoefficents(byte[,] X, byte[] Y) { int I, J, K, K1, N; N = Y.Length; for (K = 0; K < N; K++) { //First ensure that we have a non-zero entry in X[K,K] if( X[K,K] == 0 ) { for(int i = 0; i<N ; ++i ) { if(X[i,K] != 0 ) { for( ... ) //TODO: A loop to swap the entries //TODO swap entries in Y too } } if( X[K,K] == 0 ) { // TODO: Handle the case where we have a zero column // - for now we just move on to the next column // - This means we have no solutions or multiple // solutions continue } // Do full row elimination. for( int I = 0; I<N; ++I) { if( I!=K ){ //Don't self eliminate if( X[I,K] ) { for( int J=K; J<N; ++J ) { X[I,J] = X[I,J] ^ X[K,J]; } Y[J] = Y[J] ^ Y[K]; } } } } //Now assuming we didnt hit any zero columns Y should be our solution. 

}