“重置"伪随机数生成器种子多次? [英] "Resetting" pseudo-random number generator seed multiple times?

问题描述

今天，我的朋友想到了使用生成的伪随机数多次设置伪随机数生成器的种子，以使事物更加随机化".

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. 对随机性没有任何作用(即既不增加也不减少)?

伪随机数生成器的任何专家都可以提供一些详细的解释，以便我说服我的朋友吗?我很高兴看到答案解释了一些伪随机数生成器算法中的更多细节.

解决方案

伪随机数的使用有三个基本级别.每个级别都包含一个级别.

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)，因此，出于安全目的，请不要依赖这种播种形式.

Today, my friend had a thought that setting the seed of a pseudo-random number generator multiple times using the pseudo-random number generated to "make things more randomized".

An example in 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);

But I was thinking that this could probably increase the chance of getting a repeated seed being used for the pseudo-random number generator.

Will this

1. make things more randomized,
2. making it loop through a certain number of seeds used, or
3. does nothing to the randomness (i.e. neither increase nor decrease)?

Could any expert in pseudo-random number generators give some detailed explanations so that I can convince my friend? I would be happy to see answers explaining further detail in some pseudo-random number generator algorithm.

解决方案

There are three basic levels of use for pseudorandom numbers. Each level subsumes the one below it.

1. Unexpected numbers with no particular correlation guarantees. Generators at this level typically have some hidden correlations that might matter to you, or might not.
2. Statistically-independent number with known non-correlation. These are generally required for numerical simulations.
3. Cryptographically secure numbers that cannot be guessed. These are always required when security is at issue.

Each of these is deterministic. A random number generator is an algorithm that has some internal state. Applying the algorithm once yields a new internal state and an output number. Seeding the generator means setting up an internal state; it's not always the case that the seed interface allows setting up every possible internal state. As a good rule of thumb, always assume that the default library random() routine operates at only the weakest level, level 1.

To answer your specific question, the algorithm in the question (1) cannot increase the randomness and (2) might decrease it. The expectation of randomness, thus, is strictly lower than seeding it once at the beginning. The reason comes from the possible existence of short iterative cycles. An iterative cycle for a function F is a pair of integers n and k where F^(n) (k) = k, where the exponent is the number of times F is applied. For example, F^(3) (x) = F(F(F(x))). If there's a short iterative cycle, the random numbers will repeat more often than they would otherwise. In the code presented, the iteration function is to seed the generator and then take the first output.

To answer a question you didn't quite ask, but which is relevant to getting an understanding of this, seeding with a millisecond counter makes your generator fail the test of level 3, unguessability. That's because the number of possible milliseconds is cryptographically small, which is a number known to be subject to exhaustive search. As of this writing, 2^50 should be considered cryptographically small. (For what counts as cryptographically large in any year, please find a reputable expert.) Now the number of milliseconds in a century is approximately 2^(41.5), so don't rely on that form of seeding for security purposes.

这篇关于“重置"伪随机数生成器种子多次?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！