找出与给定散列相加的n个散列是否可行？

Question

考虑两组A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}；

我们可以计算这些集合的散列和：

HASHSUM()=(ℎℎ(a_1)+ ℎℎ(_2)+\cdots +ℎℎ(_))和HASHSUM()=(ℎℎ(_1) + ℎℎ(_2)+ \cdots + ℎℎ(_)).

如果$ (不一定是m)是一个很小的数字(<20)，那么set $是否可能不等于set D4，特别是HASHSUM()=HASHSUM()?。

Answer 1

让哈希长度为d。如果我们考虑有限群，像加法模2^d,一样，这个问题是很好理解的。修正了k=n+m.，如果向量是随机生成的，并且大约形成一个大小的列表，至少2^{d/k},，则存在一个具有恒定概率的解，该解与零有界。这是因为大小M的列表包含大小为k,的F:=\binom{M}{k}子集，因此，随着\{a_1,\ldots,a_n,b_1,\ldots,b_m \}在这些子集上的范围，函数f(a_1,\ldots,a_n,b_1,\ldots,b_m):=(a_1+ \cdots + a_n)-(b_1+\cdots+b_m)从\mathbb{Z}_{2^d}.命中F伪随机点。

这是一个F球，进入2^d回收箱问题，如果F\geq 2^d,，f忽略与0 \in \{0,1\}^d对应的桶的概率大致是e^{-1}\approx 0.37.，取M=\Omega((n+m) 2^{d/(n+m)})就足够了。然而，在计算上，找到解决方案的代价更高。

Wagner (参见这里 )有一个基于递归二叉树的算法，用于解决具有时间和内存复杂性的k- XOR问题x_1\oplus \cdots \oplus x_k=0 \qquad (1) --本质上是O(k 2^{d/(1+s)}). --该算法可以附加应用，如果存在解决方案，则可以解决k=n+m\geq d,的问题，因为在这种情况下将存在解决方案。

这里有+而不是\oplus,，这不是一个问题，因为我们可以使用-b_i'=2^n-b_i和使用加法自始至终。结果是，您需要F\geq d/(n+m).，所以如果d=256,和n=20,需要m\geq 236,，那么您就需要复杂O(k 2^{d/(s+1)}).。

注：对于没有模块缩减的整数情况，这相当于背包问题，对于这个问题，最好的算法具有很高的复杂度。即使您的输出在[0,2^d-1]中，添加意味着您的目标集要大得多。我相信找到一个解决方案的最佳复杂性(如果它存在，由于没有有限域而没有保证)将是O(2^{(n+m)/4}),内存和来自内存的O(2^{(n+m)/2})时间(Shamir Schroeppel?)。