多次重置“伪随机数生成器”种子有什么影响？

Question

今天，我的朋友认为使用伪随机数生成器生成的伪随机数多次设置种子可以“使事情更加随机化”。

C＃中的示例：

// Initiate one with a time-based seed
Random rand = new Random(milliseconds_since_unix_epoch());
// Then loop for a_number_of_times...
for (int i = 0; i < a_number_of_times; i++)
{
    // ... to initiate with the next random number generated
    rand = new Random(rand.Next());
}
// So is `rand` now really random?
assert(rand.Next() is really_random);

但是我认为这可能会增加伪随机数生成器使用重复种子的机会。

这将会：

1. 使事情更加随机化， 2. 让它循环一定数量的使用过的种子，或者 3. 对随机性没有影响（即既不增加也不减少）？

能否请伪随机数生成器方面的专家给出一些详细的解释，以便我能说服我的朋友？如果有人能进一步解释一些伪随机数生成器算法的细节，我将非常高兴。

- Alvin Wong

---

你最好的选择是（xkcd）掷一次骰子，然后将其用作常量。不过开个玩笑 - 计算机无法生成非伪随机数。每个真随机数都需要一个外部（例如物理测量）源进行初始化和随机性... 因此，在应用程序中使用像time.h这样的其他任何形式的普通随机数并不值得麻烦。如果您确实需要随机数，请考虑使用硬件来生成它们。 - Najzero

@Najzero 嗯，只是想更多地了解伪随机数生成器，所以我不会为此购买核衰变探测器。 :) - Alvin Wong

ffffshhh...不再有承诺，其他一切都或多或少是http://xkcd.com/221/。 - Najzero

Answer 1

有三个基本级别的伪随机数使用。每个级别都包含以下级别。

1. 没有特定相关性保证的意外数字。此级别的生成器通常具有一些可能对您有影响或可能没有影响的隐藏相关性。 2. 具有已知非相关性的统计独立数字。这通常需要用于数值模拟。 3. 不能被猜测的加密安全数字。当涉及到安全问题时，始终需要这些。

每个级别都是确定性的。随机数生成器是具有某些内部状态的算法。应用算法会产生新的内部状态和输出数字。播种生成器意味着设置内部状态；并不总是情况下，种子接口允许设置每个可能的内部状态。作为一个好的经验准则，请始终假设默认库random()例程仅在最弱的级别1上运行。

回答您的具体问题，问题中的算法(1)无法增加随机性，(2)可能会降低随机性。因此，随机性的期望严格低于一开始播种它。原因在于可能存在短迭代周期。函数F的迭代周期是一对整数n和k，其中F^(n)(k)=k，指数是应用F的次数。例如，F^(3)(x)=F(F(F(x)))。如果存在短的迭代周期，随机数将更经常地重复。在所提供的代码中，迭代函数是播种生成器然后取第一个输出。

回答您没有完全问到但与理解此问题相关的问题，使用毫秒计时器进行种子处理会使您的生成器无法通过级别3的可猜测性测试。这是因为可能的毫秒数是加密小型的，这是一个已知受到穷举搜索影响的数字。截至本文撰写时，2^50应被视为加密小型。(对于任何年份的加密大型计数，请找到值得信赖的专家。)现在，一个世纪的毫秒数大约是2^(41.5)，因此不要依赖该形式的种子处理以用于安全目的。

- eh9

Answer 2

你的例子不会增加随机性，因为没有增加熵。它只是从程序的执行时间中派生出来的。

计算机不使用基于当前时间的东西，而是维护一个熵池，并用统计上随机（或至少是无法猜测的）的数据来构建它。例如，网络数据包之间的定时延迟、按键或硬盘读取时间。

如果你想要好的随机数，你应该利用那个熵池。这些被称为密码学安全伪随机数生成器。

在C#中，查看Cryptography.RandomNumberGenerator Class以获取安全随机数的正确方法。

- Jonathan Hedley

Answer 3

这并不会使事情更加“随机”。

我们的种子确定了 rand.next() 给出的看似随机但完全确定的数字序列。

你的代码并没有使事情更加随机，而是定义了一个从初始种子到某个最终种子的映射，并且在给定相同的初始种子的情况下，你总是会得到相同的最终种子。

尝试使用这段代码玩一下，你就会明白我的意思（此外，这里有一个可以在浏览器中运行的版本链接）：

int my_seed = 100; // change my seed to whatever you want
Random rand = new Random(my_seed);
for (int i = 0; i < a_number_of_times; i++)
{
    rand = new Random(rand.Next());
}
// does this print the same number every run if we don't change the starting seed?
Console.WriteLine(rand.Next()); // yes, it does

使用此最终种子的随机对象与任何其他随机对象一样。只是创建它花费了比必要更多的时间。

- Matthew Mellott

---

但是使用当前时间呢（例如 milliseconds_since_unix_epoch()）？ - Alvin Wong

是的，使用 milliseconds_since_unix_epoch() 是生成初始种子的正确方法。在您的代码中，最终的随机对象将具有可预测转换此初始种子的种子。我提供的代码的重点是向您展示通过执行此可预测转换，您不会向系统引入任何更多的熵。 - Matthew Mellott