32 個の変数のうち 15 個を含む 32 個の xor 方程式で構成されるシステムを解かなければなりません。次のようになります。
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]16p[n]ビット整数です。
したがって、私が理解しているように、32x32 の行列 (1 と 0 のみを含む) と 32 の結果ベクトルになります。
どうやらガウスの消去法が必要なようですが、問題に頭を悩ませることはできません。そのような問題を解決する方法について誰かが私に洞察を与えることができますか?
はい、ガウス消去法を使用してこれを解決できます。重要なのは、XOR 演算が 2 を法とする加算と同等であることを認識することです。
i[0] = (p[0] + p[4] + ... ) mod 2
次に、システム全体を行列方程式として設定できます
M*p=i mod 2
通常どおりガウス消去法を使用してこれを解決できますが、すべての操作がモジュロ 2 で実行される点が異なります。行列には多数の 0 が含まれているため、ピボットを使用する必要がありますが、それ以外のアルゴリズムは同じ。
通常の連立方程式を解くことに慣れている場合、これは大きなステップアップではありません。連立方程式で実数を使用する場合、次のように消去します。
[a b; c d] -> [a b; 0 d-(b*c/a)] -> [a 0; 0 d-(b*c/a)] -> [1 0; 0 1]
注:ここでは、簡単に入力できるように MATLAB 行列表記を使用します。
これらの行列演算 (つまり、除算、乗算、加算、および減算) はすべて、実数だけでなく、任意のフィールドに存在することに注意してください。フィールドという用語に慣れていない場合は、乗算、否定、反転、加算などを可能にする値のグループを意味します。
これにより、xor 方程式系を解くことができます。あなたは現在、あなたのシステムを、xor'd された 16 ビット値の束として説明しています。しかし、私が選択した方法は、xor で結合されたビットの束として表現することでした。たとえば、最初の式が次の場合:
p[0] = a[1] ^ a[2]
これを次のように表します。
p[0][0] = a[1][0] ^ a[2][0]
p[0][1] = a[1][1] ^ a[2][1]
…
括弧の 2 番目のセットはbit、16 ビット値のオフセットを示します。したがって、それぞれの小さな方程式は 16 個の方程式に相当します。
ブール値に対する単一ビット xor 演算は、フィールドを形成します。このフィールドでは、「加算」演算子を 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() メソッドを見ることを特にお勧めします。