我要解决一个系统，它由32个异或方程组，每个涉及15 32的变量。 其中一个是这样的：

的 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]
 

我[n]和P [N]是16位整数。

因此​​，正如我理解，我可以结束了一个32×32的矩阵（只包含1和0），以及32结果向量。

显然，高斯消元法是我需要的，但我不能环绕这个问题我的脑海里，可能有人给我如何解决这样的问题一些见解？

编辑：这是C ++的解决方案

 无效SolveLinearSystem（U8 A [32] [32]，U8 B〔32〕）
{
INT N = 32;
为（中间体K = 0; K＆所述N; ++ K）的
{
    如果（A [K] [K] == 0）
    {
        对于（INT I = K + 1;我n种; ++ I）
        {
            如果（A [1] [K]！= 0）
            {
                为（中间体L = 0; L＆所述N; ++ L）的
                {
                    INT S = A [K] [L]
                    A [K] [1] = A [1] [1];
                    A [1] [1] = S;
                }
                int类型= B [I]
                乙[I] = B [K];
                乙[K] = S;
                    打破;
            }
        }
    }

    的for（int i = 0; I＆所述N; ++ I）
    {
        如果（我！= K）
        {
            如果（A [1] [K]）
            {
                INT M = 0;
                为（M = K，M＆所述N; ++ M）的
                {
                    A [1] [M] = A [I] [M] ^ A [K] [M]。
                }
                乙[Ⅰ] = B [Ⅰ] ^ B [K];
            }
        }
    }
}
}
 

解决方案

是的，你可以用高斯消元法来解决这个问题。关键是要认识到，异或操作相当于增加模2。所以你写的公式等同于

  I [0] =（P [0] + P [4] + ...）模2
 

然后，您可以将整个系统作为一个矩阵方程

  M * P = Imod2
 

您可以解决这个用高斯消元像往常一样，不同之处在于所有的操作都​​将被执行模2.由于您的基质含有大量的0，那么你将不得不使用旋转，但除此之外，在算法是相同的。

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];
            }
        }
    }
}
}

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.