algorithm - 是否有可能基于有限的伪随机数序列获得种子的近似值？

Question

假设我有一些形成系列的数字，例如：652,328,1,254，我想得到一个种子，例如，如果我这样做

srand(my_seed);

当所有数字都以相同的顺序出现时，我会得到某种对我的原始序列有界误差的近似值。

score 3 · Accepted Answer

取决于用于伪随机生成的算法。如果算法是一个简单的线性同余生成器，那么取回种子只是求解线性模方程的问题（请注意，解可能是非唯一的，但由于这样的生成器是无记忆的，它不会事情）。

如果算法更复杂，这可能是不可能的。

请注意，C 标准库中使用的算法不受标准限制，因此不同的平台可能有不同的实现。

score 1 · Accepted Answer

看看这个问题。

rand()正如贾斯汀所说，当你有一系列生成的数字时，可以回溯线性全等生成器（通常是实现）。我想问题是要知道以前的哪个值是原始种子...

score 1 · Accepted Answer

一般来说，您不能有错误限制。你的算法要么有效，要么无效。原因是合理的误差界限显然比 RAND_MAX 小得多。这反过来意味着低位不像高位那样随机。但是一个好的 PRNG 可以确保所有位都是同样随机的。

考虑一下这个缓慢但数学上合理的 RNG 算法示例：

int rand() {
  state = AES_encrypt(state);
  return state % RAND_MAX;
}
void srand(int seed) {
  state = AES_encrypt(seed);
}

如果您可以发现输出序列与前一个序列之间存在任何显着相关性state，则应认为 AES 算法已损坏。

score 1 · Accepted Answer

加密 PRNG 的定义是，这种确切的属性在计算上是不可行的——但是，正如已经提到的，有更弱（和更快）的 PRNG 是可能的。所以这取决于你的算法。

4 回答 4