问用时间换取空间

EN

用一点钱就可以构建一台能够处理35万亿次浮点运算的服务器。这大约是每秒2^45次操作，考虑到开销和其他因素，我认为生成32-40比特的信息可以在一秒内完成。一个1MB的文件可能需要大约70个小时才能生成，每秒32位。

我在脑海中有一个特定的用例，从100KB“解压缩”一个1MB文件需要700个小时。我熟悉鸽子洞原理，生日悖论，以及为什么递归压缩是不可能的。然而，固执地认为我们可以枚举所有32位的可能性，匹配一些散列函数输出或一些蛮力方法，并利用数学的本质来帮助缩小问题空间。

我最初是通过使用sha-256或其他还没有发现冲突的散列函数来思考这个问题的(尽管在给定鸽洞的情况下，与任何散列函数都有无限多的冲突，但如果我碰巧遇到了sha-256的冲突，那么至少它对研究来说是有意义和重要的)。

提供224位的原始数据以及256位散列。信息的最后32位被枚举，直到找到该散列的匹配。现在，存储224+256位的信息以取回256位实际上不是任何类型的数据压缩，但它是第一次想到的方法。

最大的开销是发送散列，所以我尝试了像CRC32这样的32位散列函数，但是冲突的概率太高了。看起来普通的哈希是不可行的，你需要哈希的输出小于我们可以合理计算的值(~40位)，并且没有足够的哈希空间来避免冲突。现在，如果我们可以做2^256次计算(量子？)则可以使用256位散列，因为冲突的概率低到足以可用。

我研究了一点位置敏感的散列函数，希望在给定位置的情况下，即使散列大于32位，我也可以将问题空间限制为2^32次计算，但这并没有真正显示出有希望

我正在寻找关于如何验证和生成数据的想法/建议，假设您有大约100天的时间来解压缩/生成给定的今天的计算能力(不到10K美元的设备，但ASIC/FPGA是公平的游戏)。可以理解的是，我可能正在追求一些不可行甚至不可能的东西，但探索这些想法并扩展我的计算机科学知识胜过整天玩视频游戏。