0

这个问题与语言无关,所以我请各位聪明的程序员以某种方式帮助我。

给定的是一组带有 |M| 的元素“M” = 2^128 个元素。每个元素“m”的位长为 128 位。

我想发送一条长度为 128 位的消息。在此消息中,我想合并 M 的元素之一和一些信息“n”。这意味着,“m”和“n”的长度必须 < 128 位(消息的长度)。

对方拥有所有元素的完整集合“M”,但我需要告诉他/她她/他必须使用哪个元素。该指令必须适合一条消息,并且不能拆分为多条消息。

所以,我想用算法 f() 索引我的元素,以便 f(m)=index_of_m 和 index_of_m<128 位。

换句话说,该算法必须将 2^128 个长度为 128 位的元素映射到一个索引上,该索引用比元素长度(128 位)更少的位表示。

再次正式:

套装:

M=(m1,m2,...mn) with n = 2^128

每个长度m1...mn: 128 bits.

一条消息"n" < 128 bit。消息长度是可变的,可以是 1 位。

索引/映射函数:f()

f(m1)=i1  Index 1 of element m1 with the length of i1 < 128 bit., so i1+n=128bit
Wanted: Function f().

想法:

- 哈希不会以简单的方式对元素进行哈希处理,因为具有 64 位输出的哈希可以对 2^128 个元素进行编码。具有 128 位输出的哈希将用完整个消息,并且“n”将没有位置。

- 从 1 到 2^128 的索引不起作用,例如,2^128 将用完整个消息。

4

1 回答 1

2

不。

如果“一个集合”是指一个集合,即没有重复的元素并且顺序无关紧要,那么您的 M 只是 0..2 128 -1 范围内的所有整数的集合。

对于所有元素,没有小于 128 位的 M 的所有元素的表示。如果有,那么仅仅通过计数,没有足够的表示来映射到所有元素,这是一个矛盾。

于 2013-05-27T17:42:43.777 回答