Solving a large system of linear equations over the finite field F2

I have 10163 equations and 9000 unknowns, all over finite fields, like this style:

Of course my equation will be much larger than this, I have 10163 rows and 9000 different x.

Presented in the form of a matrix is AX=B. A is a 10163x9000 coefficient matrix and it may be sparse, X is a 9000x1 unknown vector, B is the result of their multiplication and mod 2.

Because of the large number of unknowns that need to be solved for, it can be time consuming. I'm looking for a faster way to solve this system of equations using C language.

I tried to use Gaussian elimination method to solve this equation, In order to make the elimination between rows more efficient, I s开发者_如何学Ctore the matrix A in a 64-bit two-dimensional array, and let the last column of the array store the value of B, so that the XOR operation may reduce the calculating time.

The code I am using is as follows:

    uint8_t guss_x_main[R_BITS] = {0};
    uint64_t tmp_guss[guss_j_num];

    for(uint16_t guss_j = 0; guss_j < x_weight; guss_j++)
    {
      uint64_t mask_1    = 1;
      uint64_t mask_guss = (mask_1 << (guss_j % GUSS_BLOCK));
      uint16_t eq_j      = guss_j / GUSS_BLOCK;
      for(uint16_t guss_i = guss_j; guss_i < R_BITS; guss_i++)
      {
        if((mask_guss & equations_guss_byte[guss_i][eq_j]) != 0)
        {
          if(guss_x_main[guss_j] == 0)
          {
            guss_x_main[guss_j] = 1;
            for(uint16_t change_i = 0; change_i < guss_j_num; change_i++)
            {
              tmp_guss[change_i] = equations_guss_byte[guss_j][change_i];
              equations_guss_byte[guss_j][change_i] =
                  equations_guss_byte[guss_i][change_i];
              equations_guss_byte[guss_i][change_i] = tmp_guss[change_i];
            }
          }
          else
          {
            GUARD(xor_64(equations_guss_byte[guss_i], equations_guss_byte[guss_i],
                         equations_guss_byte[guss_j], guss_j_num));
          }
        }
      }
      for(uint16_t guss_i = 0; guss_i < guss_j; guss_i++)
      {
        if((mask_guss & equations_guss_byte[guss_i][eq_j]) != 0)
        {
          GUARD(xor_64(equations_guss_byte[guss_i], equations_guss_byte[guss_i],
                       equations_guss_byte[guss_j], guss_j_num));
        }
      }
    }

R_BIT = 10163, x_weight = 9000, GUSS_BLOCK = 64, guss_j_num = x_weight / GUSS_BLOCK + 1; equations_guss_byte is a two-dimensional array of uint64, where x_weight / GUSS_BLOCK column stores the matrix A and the latter column stores the vector B, xor_64() is used to XOR two arrays, GUARD() is used to check the correctness of function operation.

Using this method takes about 8 seconds to run on my machine. Is there a better way to speed up the calculation?