algorithm - 将一组整数中的哪些整数进行异或以生成目标整数？

Question

给出的是：

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

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

• 同一类型的目标整数17358988457627394926，在大多数情况下不在集合中。

保证目标整数是通过对集合中最多 50 个（或更少）整数的子集进行异或运算得到的。

什么是最有效的算法来找到一个整数子集（任何，不一定是最小的）在异或时成为目标整数的整数？

如果 NP 难，证明它的基本思想是什么？

Answer 1

工作在 Z ₂上，问题等价于求解矩阵方程Ax = b，其中A是 64x800 二进制矩阵，是对每个元素进行二进制展开，b是表示解的 64 元素二进制矩阵。

使用简单的高斯消元法很容易解决这样的系统。