3

今天，我的朋友有一个想法，使用生成的伪随机数多次设置伪随机数生成器的种子，以“使事情更随机化”。

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. 对随机性没有任何影响（即既不增加也不减少）？

有哪位伪随机数生成器方面的专家能给出一些详细的解释，以便我可以说服我的朋友吗？我很高兴看到答案解释了一些伪随机数生成器算法的更多细节。

4

3 回答 3

8

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

  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)，所以不要为了安全目的而依赖这种形式的播种。

于 2012-12-10T19:34:05.267 回答
1

Your example won't increase the randomness because there is no increase in entropy. It is simply derived from the execution time of the program.

Instead of using something based of the current time, computers maintain an entropy pool, and build it up with data that is statistically random (or at least, unguessable). For example, the timing delay between network packets, or key-strokes, or hard-drive read times.

You should tap into that entropy pool if you want good random numbers. These are known as Cryptographically secure pseudorandom number generators.

In C#, see the Cryptography.RandomNumberGenerator Class for the right way to get a secure random number.

于 2012-12-17T00:28:15.413 回答
0

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

我们的种子决定了 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

带有这个最终种子的 Random 对象就像任何其他 Random 对象一样。它只是花了你更多的时间而不是必要的时间来创建它。

于 2012-12-08T16:48:06.543 回答