哪个整数从一组整数到XOR来制作目标整数？

Question

鉴于:

• 一组约800个伪随机无符号64位整数.

  2910088619203924111,  8611579852607706360,  10743563285097812384,
  6712886796489718596, 17298387234720051377,  12467698534877227789,
  3782074590599432740,  1419307814092336225,   7951308495700413025,
  ...

• 17358988457627394926相同类型的目标整数,大多数情况下不在集合中.

保证目标整数是通过对该组的最多50个(或更少)整数的子集进行异或来产生的.

什么是最有效的算法来找到在XORed时生成目标整数的整数(任何,而不是必须最小)的整数？

如果NP难,那么证明它的基本想法是什么？

Answer 1

在Z _2中工作,问题等同于找到矩阵方程的解Ax = b,其中A64x800二进制矩阵通过采用每个元素的二进制展开而形成,并且b是表示解的64元素二进制矩阵.

使用直接的高斯消元法很容易解决这样的系统.