求解XOR方程組

Question

我必須求解一個由32個xor方程組成的系統，每個方程包含32個變量中的15個。 一個看起來像這樣：

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]和P [N]爲16個整數。

所以，據我所知，我最終會得到一個32x32矩陣（只包含1s和0s）和一個32結果向量。

顯然高斯消除是我所需要的，但我無法繞開這個問題，有人能給我一些關於如何解決這個問題的見解嗎？

編輯：這裏是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

是的，你可以用高斯消元法來解決這個問題。關鍵是要認識到，XOR操作相當於增加模2.所以，你寫的公式等同於

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

然後，您可以設置整個系統最高爲矩陣方程

M*p=i mod 2 

你可以像平常一樣使用高斯消元來解決這個問題，除了你所有的操作都是以模2來執行的。由於你的矩陣包含很多的0，所以你將不得不使用pivoting，但除此之外，算法是相同。

Answer 2

如果您熟悉求解常規方程組，這不是主要步驟。當方程的系統使用實數，你消除像這樣：

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

注：這裏我用MATLAB矩陣符號爲便於入境。

要做出的重要實現是所有這些矩陣運算（即除法，相乘，加法和減法）都存在於任何字段中，而不僅僅是實數。如果您不熟悉術語字段，它只是意味着一組允許乘法，否定，倒置，加法等的值。

這需要我們去求解xor方程組。您目前將您的系統描述爲一組16位值。不過，我選擇了它表示爲一串比特的方式一起進行異或，舉例來說，如果你的第一個方程爲：

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

我的方式來表示：

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

其中第二組括號表示16位值中的bit偏移量。所以，你的每個小方程將相當於16個方程。

布爾值上的單比特異或操作形成一個字段。在這個領域，我們使「加法」運算符等於xor。我們可以定義加法和乘法表如下：

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

司只能由1（因爲你不能除以零），因此，除操作留下一個元素保持不變。

有了這個，你應該能夠爲你的xor方程組形成一個矩陣。這個矩陣將完全由1和0組成。然後使用gauss-jordan消除算法（實現起來並不難），就像對普通實數一樣。這將允許您反轉矩陣並找到解決方案。

我個人對這個問題非常感興趣，我寫了一個小的C++矩陣實現，允許您提供任何你喜歡的字段。這可能是一個很好的起點，或者你甚至可能希望完全使用我的代碼！以下是Github上的源代碼：XorSystem。我特別建議查看ANMatrix上的invert（）方法。