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

疑似乱数の使用には、3つの基本的なレベルがあります。各レベルには、その下のレベルが含まれます。

  1. 特定の相関関係が保証されていない予期しない数値。このレベルのジェネレーターには、通常、重要な場合とそうでない場合がある、いくつかの隠れた相関関係があります。
  2. 既知の非相関を持つ統計的に独立した数。これらは通常、数値シミュレーションに必要です。
  3. 推測できない暗号的に安全な数値。これらは、セキュリティが問題になる場合は常に必要です。

これらのそれぞれは決定論的です。乱数ジェネレーターは、内部状態を持つアルゴリズムです。アルゴリズムを1回適用すると、新しい内部状態と出力番号が生成されます。ジェネレーターのシードとは、内部状態を設定することを意味します。シードインターフェイスですべての可能な内部状態を設定できるとは限りません。経験則として、デフォルトのライブラリrandom（）ルーチンは、最も弱いレベルであるレベル1でのみ動作すると常に想定してください。

あなたの特定の質問に答えるために、質問のアルゴリズムは（1）ランダム性を増やすことができず、（2）それを減らすかもしれません。したがって、ランダム性の期待値は、最初に1回シードするよりも厳密に低くなります。その理由は、短い反復サイクルが存在する可能性があるためです。関数の反復サイクルFは整数のペアでnあり、kここF^(n) (k) = kで、指数は回数Fです。たとえば、F^(3) (x) = F(F(F(x)))。反復サイクルが短い場合、乱数はそうでない場合よりも頻繁に繰り返されます。提示されたコードでは、反復関数はジェネレーターをシードしてから最初の出力を取得することです。

あなたが完全には尋ねなかったが、これを理解することに関連する質問に答えるために、ミリ秒のカウンターでシードすると、ジェネレーターはレベル3のテストに失敗します。これは、可能なミリ秒数が暗号的に小さいためです。これは、徹底的な検索の対象となることがわかっている数値です。この記事の執筆時点では、2^50は暗号的に小さいと見なす必要があります。（どの年でも暗号的に大きいと見なされるものについては、評判の良い専門家を見つけてください。）現在、1世紀のミリ秒数は約2 ^（41.5）なので、セキュリティの目的でその形式のシードに依存しないでください。

于 2012-12-10T19:34:05.267 に答える
1

エントロピーが増加しないため、例ではランダム性は増加しません。これは、プログラムの実行時間から単純に導き出されます。

コンピューターは、現在の時刻に基づいたものを使用する代わりに、エントロピープールを維持し、統計的にランダムな（または少なくとも推測できない）データでエントロピープールを構築します。たとえば、ネットワークパケット間のタイミング遅延、キーストローク、またはハードドライブの読み取り時間。

適切な乱数が必要な場合は、そのエントロピープールを利用する必要があります。これらは、暗号論的に安全な疑似乱数ジェネレータとして知られています。

C＃では、安全な乱数を取得する正しい方法について、 Cryptography.RandomNumberGeneratorクラスを参照してください。

于 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 に答える