这颗默森Twister种子是如何被先验发现的，用于一个20个字符的字符串？

Question

有人为Mersenne Twister制作了一颗种子，目的是让这个种子产生这个字符串：

"9!dlroW ,olleH"ck,@

有20个字符长。他为什么这么做在下面解释，但我不知道他是怎么黑的。

他为什么这么做：

用户feersum上的代码高尔夫这样做，以产生一个你好，世界！用种子编程语言编程。显然，他并不仅仅是用蛮力强迫自己进入这种种子，它的长度为4200位。他是怎么做到的？此外，这个用户还有其他答案，他在其中使用的可能是相同的技巧，参见：这个答案。

我们所知道的:种子往往是相当大的(大得多，如果他们是畜生的加法和世代强迫)。此外，他发现的每一个种子都必须用种子生成624个整数，然后再扭曲下一个20来生成上面字符串的数值数据。对n长的字符串施加蛮力的复杂性是O(96^n)，确实非常复杂。

我怀疑的是:他过滤他产生的种子，从而将n长度的复杂度降低到大约O(log(96^n))，从而简化为O(1)。我不认为“他可以使用超级计算机”是一个可行的答案。

一个可以接受的答案:任何能解释他是如何做到这一点的东西，即使他的做法是不同的。可能需要很长一段时间才能知道这个问题的答案。

有趣的Mersenne琐事:你可以用624个输出来生成Mersenne的状态，然后预测它的未来输出。

注:在“你好，世界”上有几个赏金承诺！问他是否要解释他是怎么做到的。几年过去了，他一点也不动摇。也许那些赏金会因为你解释了这件事而转嫁给你。

Answer 1

他是怎么做到的？

事实上，当你提到：

您可以用624个输出来生成Mersenne龙卷风的状态，然后从它预测未来的输出。

这是真的，但是你可以用它做其他的事情。您还可以生成先前的输出(即Mersenne twister输出将在所看到的块上的输出)、以前的状态(即龙卷风状态必须是什么，以便在经过龙卷风的迭代之后得到所选的状态)，并计算获得特定状态所需的种子。

因此，最有可能的是他所做的事情：

• 创建了一个由"9!dlroW ,olleH"ck,@ (20个字节或5个整数)组成的624个整数的输出，以及619个任意值。这些最后的619个整数将被忽略，因此您为它们选择了什么值并不重要。
• 重建产生此输出所需的内部扭转状态。
• 生成在经过扭曲排列之后生成此状态所需的以前的扭曲状态。
• 生成生成这种扭曲状态所需的种子。

就是这样。上面的手工操作有点繁琐；对于程序来说，这是相当琐碎的。