一尘不染

如何求解XOR方程组?

algorithm

我必须解决一个由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矩阵(仅包含1和0)和32个结果向量。

显然,我需要高斯消除法,但我无法解决这个问题,有人可以给我一些有关如何解决此类问题的见解吗?


阅读 280

收藏
2020-07-28

共1个答案

一尘不染

是的,您可以使用高斯消除法解决此问题。关键是要认识到XOR运算等效于加法模2。因此,您编写的方程式等效于

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

然后,您可以将整个系统设置为矩阵方程式

M*p=i mod 2

您可以像往常一样使用高斯消去法来解决这个问题,除了您的所有运算将以模2进行。由于矩阵包含很多0,因此您将不得不使用数据透视,但除此之外,算法是相同。

2020-07-28