寻求比中间相遇更优的GF(2)下k个向量模2和为目标值的求解算法

针对k远小于维度时的优化方案 #

你提到的观察是完全正确的：k个向量的模2和最多张成k维空间，这个特性可以用来构造远快于朴素中间相遇的求解方案，这类问题本质属于GF(2)上线性方程组的低汉明重量解搜索，成熟的优化方法如下：

• 优先使用信息集解码（ISD）类算法：你可以把问题转化为矩阵方程求解形式：将n个输入向量作为列构造64行n列的矩阵M，问题等价于寻找长度为n、恰好包含k个1的0-1向量x，满足M * x = T (mod 2)。信息集解码算法就是专门针对这类低重量解搜索设计的，当k远小于维度和n时，时间复杂度远低于O(n^{{k/2})。以k=16、n=256的场景为例，优化后的ISD算法可以将运算量控制在2}20量级，普通消费级CPU就能在秒级出结果。
• 轻量化实现可选分层投影剪枝：如果不想实现复杂的ISD，可以先用随机掩码对64位向量做低维投影（比如投影到24位），提前过滤掉绝大多数无效的k元组合，再结合中间相遇做搜索，通常也能获得1~2个数量级的速度提升。

关于缩减向量集到64个的疑问 #

你的顾虑是合理的：直接任选64个张成全空间的向量，无法保证刚好选k个的解存在于这个子集里。但你可以对这个思路做变形来避免违反k的限制：

1. 先对全部n个向量做高斯消元，记录每个基向量对应的原始向量组合系数，以及每个非基向量对应的基的线性组合关系
2. 先将目标T表示为基向量的线性组合，再还原为原始向量的组合，得到一个任意重量的初始解
3. 利用「任意非基向量和它对应的基组合的模2和为0」的性质，通过增减这类和为0的组合来调整解的总重量，直到刚好等于k即可。题目已经保证解存在，因此这个调整过程一定可以完成。

内容的提问来源于stack exchange，提问作者ketsi