0

疑似乱数の生成について説明したいと思います。私の質問は次のとおりです。

  • 疑似乱数生成で繰り返し番号を取得する可能性はありますか？

  • グーグルで検索すると、真の乱数生成が見つかりました。真の乱数生成のためのいくつかのアルゴリズムを取得して、次のように使用できるようにすることはできますか？

    SecureRandom.getInstance（文字列アルゴリズム）

セキュリティを優先してご指導ください。

4

4 に答える 4

4

1）はい、通常、PRNGでは番号を繰り返すことができます。実際、鳩の穴の原理を適用する場合、証明は非常に簡単です（つまり、32ビットの符号なし整数のセットにPRNGがあると仮定します。2^ 32を超える疑似乱数を生成する場合は、確かに次のようになります。少なくとも1つの数値が少なくとも2回生成されます。実際には、それははるかに高速に発生します。通常、PRNGのアルゴリズムはシーケンスを循環し、そのサイクルのサイズを計算または推定する方法があります。単一の数値が繰り返され始め、アルゴリズムのイメージは通常、数値を取得するセットよりもはるかに小さくなります）。

繰り返されない番号が必要な場合（セキュリティが懸念されるため、繰り返し番号を許可する一連の（疑似）乱数よりも安全性が低いことに注意してください!!!）、次のように実行できます。

class NonRepeatedPRNG {
  private final Random rnd = new Random();
  private final Set<Integer> set = new HashSet<>();
  public int nextInt() {
    for (;;) {
      final int r = rnd.nextInt();
      if (set.add(r)) return r;
    }
  }
}

nextInt上で定義されたメソッドは決して返されないことに注意してください！注意して使用してください。

2）いいえ、「真の乱数生成のアルゴリズム」のようなものはありません。アルゴリズムは既知のものであり、制御および予測できます（つまり、実行するだけで出力が得られます。出力は正確にわかります。次回、同じ初期条件で実行した場合）、真のRNGは定義上完全に予測できません。

最も一般的なセキュリティ関連ではないアプリケーション（つまり、科学計算、ゲームなど）の場合、PRNGで十分です。セキュリティが懸念される場合（つまり、暗号に乱数が必要な場合）、CSPRNG（暗号論的に安全なPRNG）で十分です。

真のランダム性なしでは動作しないアプリケーションがある場合、私はそれについてもっと知りたいと思っています。

于 2013-03-09T06:59:34.727 に答える
3

はい、どの乱数ジェネレーターでも繰り返すことができます。重複しない乱数の問題には、次の3つの一般的な解決策があります。

  • 広い範囲からいくつかの番号が必要な場合は、1つを選択し、重複している場合は拒否します。範囲が広い場合、これによって何度も試行が繰り返されることはありません。

  • 狭い範囲から多くの数値が必要な場合は、すべての数値を配列に設定し、配列をシャッフルします。フィッシャー-イェーツアルゴリズムは、アレイシャッフルの標準です。シャッフルされた配列から順番に乱数を取得します。

  • 広い範囲から多数の数値が必要な場合は、適切なサイズの暗号化アルゴリズムを使用してください。たとえば、64ビット番号の場合はDESを使用し、0、1、2、3、...を順番に暗号化します。暗号化は可逆的であるため、出力は一意であることが保証されます。

于 2013-03-09T10:03:02.047 に答える
0

疑似RNGは自分自身を繰り返すことができますが、真のRNGも自分自身を繰り返すことができます。自分自身を繰り返さなかった場合、ランダムにはなりません。

ある程度の（〜128ビット）実際のエントロピーがシードされた優れたPRNGは、実際には実際のRNGと区別できません。確かに、真のRNGよりも著しく多くの衝突や繰り返しが発生することはありません。

したがって、真の乱数ジェネレーターが必要になる可能性はほとんどありませんが、必要な場合は、random.orgでHTTPAPIを確認してください。彼らのAPIは、真のランダムソースに支えられています。ランダム性は大気ノイズに由来します。

于 2013-03-09T10:23:52.430 に答える
0

PRNGまたはRNGが数値を繰り返さなかった場合、それは...実際には予測可能です。1から8までの数字のPRNGを想像してみてください。2、5、7、3、8、4、6の数字が出力されます。PRNGが繰り返さないように一生懸命努力した場合、次の数字は次のようになります。 1-それはもうランダムではありません！

したがって、PRNGとRNGは、デフォルトで繰り返しのあるランダムな出力を生成します。繰り返したくない場合は、Fisher-Yates Shuffle（http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle）のようなシャッフルアルゴリズムを使用して、数字の配列をランダムにシャッフルする必要があります。ランダムな順序で欲しい。

また、暗号化の目的で乱数生成のソースが必要な場合は、ご使​​用の言語の暗号化PRNGのプロバイダーを探してください。暗号的に強力である限り、問題はありません。真のRNGははるかに高価であり（またはrandom.orgを使用するなどの遅延が必要です）、通常は必要ありません。

于 2013-04-11T06:09:59.840 に答える