如何找到哪个位域与另一个位域异或? [英] How to find which subset of bitfields xor to another bitfield?

问题描述

我有一个数学问题.我有一堆位域，想计算它们的哪个子集，以进行异或运算以达到某个其他位域，或者，如果没有一种方法可以发现不存在这样的子集.

I have a somewhat math-oriented problem. I have a bunch of bitfields and would like to calculate what subset of them to xor together to achieve a certain other bitfield, or if there isn't a way to do it discover that no such subset exists.

我想使用一个免费的库而不是原始代码来执行此操作，并且我强烈希望使用Python绑定(也可以使用Python的内置数学库，但是我想移植它)最终使用多种语言).同样，最好不要因为不必将每个位扩展到自己的字节而浪费存储空间.

I'd like to do this using a free library, rather than original code, and I'd strongly prefer something with Python bindings (using Python's built-in math libraries would be acceptable as well, but I want to port this to multiple languages eventually). Also it would be good to not take the memory hit of having to expand each bit to its own byte.

需要进一步澄清:我只需要一个解决方案.我的矩阵与稀疏相反.我对将运行时保持在绝对最低限度非常感兴趣，因此强烈建议使用算法奇特的方法来转换矩阵.另外，将给定的特定位域输出是非常重要的，因此仅找到将xor设为0的子集的技术就不能完全消除它.

Some further clarification: I only need a single solution. My matrices are the opposite of sparse. I'm very interested in keeping the runtime to an absolute minimum, so using algorithmically fancy methods for inverting matrices is strongly preferred. Also, it's very important that the specific given bitfield be the one outputted, so a technique which just finds a subset which xor to 0 doesn't quite cut it.

我通常知道高斯消除.我试图避免从头开始！

And I'm generally aware of gaussian elimination. I'm trying to avoid doing this from scratch!

交叉发布到mathoverflow，因为尚不清楚此问题的正确位置是-

cross-posted to mathoverflow, because it isn't clear what the right place for this question is - https://mathoverflow.net/questions/41036/how-to-find-which-subset-of-bitfields-xor-to-another-bitfield

推荐答案

从数学上讲，可以将两位的XOR视为F_2字段中的加法.

Mathematically speaking, XOR of two bits can be treated as addition in F_2 field.

您想在F_2字段中求解一组方程.对于具有位(a_0，a_1，... a_n)，(b_0，b_1，...，b_n)，(c_0，c_1，...，c_n)，(r_0，r_1，...，r_n的四个位域)，则得到方程式:

You want to solve a set of equations in a F_2 field. For four bitfiels with bits (a_0, a_1, ... a_n), (b_0, b_1, ..., b_n), (c_0, c_1, ..., c_n), (r_0, r_1, ..., r_n), you get equations:

x * a_0 + y * b_0 + z * c_0 = r_0
x * a_1 + y * b_1 + z * c_1 = r_1
...
x * a_n + y * b_n + z * c_n = r_n

(您在其中查找x，y，z的地方).

(where you look for x, y, z).

您可以使用glpk(可能是lp_solve)将其编程为简单的整数线性问题(但我不记得它是否适合).但是，这些方法可能会非常缓慢地起作用，因为它们正在尝试解决更为普遍的问题.

You could program this as a simple integer linear problem with glpk, probably lp_solve (but I don't remember if it will fit). These might work very slowly though, as they are trying to solve much more general problem.

搜索了一段时间后，看来页面可能是寻找代码的好开始.从描述看来，Dixon和LinBox可能是一个很好的选择.

After googling for a while, it seems that this page might be a good start looking for code. From descriptions it seems that Dixon and LinBox could be a good fit.

无论如何，我认为在mathoverflow上提问可能会为您提供更准确的答案.如果您这样做，请在此处链接您的问题.

Anyway, I think asking at mathoverflow might give you more precise answers. If you do, please link your question here.

更新: Sagemath 使用

Update: Sagemath uses M4RI for solving this problem. This makes it (for me) a very good recommendation.

这篇关于如何找到哪个位域与另一个位域异或?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！