如何求解XOR方程组？ [英] How to solve systems of XOR equations?

问题描述

我必须解决一个包含32个异或方程的系统，每个方程包含32个变量中的15个。
一个看起来像这样：

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] 和 p [n] 是16位整数。

明白我最终将得到一个32x32矩阵（仅包含1和0）和32个结果向量。

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?

推荐答案

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

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

您可以像往常一样使用高斯消除来解决此问题，除了所有运算将以模2进行。 0s，那么您将不得不使用数据透视，但是除此之外，算法是相同的。

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.

这篇关于如何求解XOR方程组？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！