18

関数が本当にランダムであるか、概念にできるだけ近いことをどのように確認できますか？また、ランダムと疑似ランダムの違いは何ですか？最後に、乱数を生成するために使用できるアルゴリズム/ソースは何ですか？

PS：を使用したMySQLステートメントORDER BY RAND() LIMIT 1は説得力のある結果をもたらさないため、これも尋ねます。

4

7 に答える 7

18

ランダムであるということは、ランダム関数からの戻り値がランダムかどうかわからないということです。

XKCD

...また...

ディルバート

適切なランダムでは、ホワイト ノイズなど、真にランダムになり得るものを使用します。疑似乱数は一般に、数式または事前に計算されたテーブルから計算されます。線形合同ジェネレーターは、それらを生成する一般的な方法です。

実際の乱数を取得するには、通常、何かが有機的に生成された外部ソースとやり取りする必要があります。これは真の乱数ジェネレーターと呼ばれます。

于 2011-06-22T10:11:51.023 に答える
12

アロハ！

ランダム性をテストするには、いくつかの方法とツールがあります。これらは、テスト対象のジェネレーターから収集された一連の数値に適用されます。つまり、生成された一連のデータに基づいてジェネレーターをテストします。

コンピューティングでは、特に IT セキュリティでは、通常、一様乱数プロセスに準拠するジェネレーターが必要です。いろいろな工程がありますが、目指しているのは統一された工程だと思います。

NIST は、疑似乱数ジェネレーターとそれらのテスト方法の両方に関する推奨事項を含むいくつかのドキュメントを公開しています。NIST ドキュメント SP 800-22 および SP 800-20 を参照してください。

他の誰かが指摘したように。True Random Number Generator (TRNG) が必要な場合は、物理エントロピーを収集する必要があります。このようなソースの例は、放射性崩壊、宇宙放射線、溶岩ランプなどです。できれば、操作が難しいソースが必要です。IETF には、いくつかの適切な推奨事項がある RFC があります。RFC 4086 - Source of Randomness for Security を参照してください: https://www.rfc-editor.org/rfc/rfc4086

通常行うことは、1 つ以上 (できれば複数) のソースからエントロピーを収集することです。収集されたデータはフィルター処理 (ホワイトニング) され、最終的には適切な PRNG を定期的にシードするために使用されます。当然のことながら、異なる種子を使用します。

これは、最新の優れた乱数発生器のほとんどが機能する方法です。対称暗号 (AES など) やハッシュ関数などの暗号プリミティブを使用して作成された PRNG を供給するエントロピー コレクター。たとえば、Schneier による乱数発生器 Yarrow/Fortuna を参照してください。これは、変更された形で FreeBSD で使用されています。

テストに関する質問に戻ります。誰かが指摘したように、Marsaglia は DIEHARD テストで体系化された一連の優れたテストを作成しました。Dieharder テストには、さらに拡張された一連のテストがあります: http://www.phy.duke.edu/~rgb/General/dieharder.php

Dieharder は、それに供給される (ジェネレーターから収集された) 大量の数値がランダム (高品質) であるかどうかを確信できる優れたツールです。Dieharder の実行は簡単ですが、時間がかかります。

ランダム性のその場でのテストは困難です。通常、システムに Dieharder を実装する必要はありません。できることは、病的なケースを検出するいくつかの単純な検出器を実装することです。私は通常お勧めします：

  • 値の長さが等しい。RNG によって生成された 2 つの連続する値が異なるたびにリセットされる単純なカウンター。そして、RNG が壊れていることをカウンターが示していると思われる場合は、しきい値を定義する必要があります。1000 万個の等しい値が表示され、値空間が 1 つの値 (表示されている値) よりも大きい場合、RNG はおそらく十分に機能していません。特に、表示されている値がエッジ値の 1 つである場合。たとえば、0x00000.... または 0xfffff...

  • 中央値。100 万の値を生成した後、一様な分布を持つ中央値が値空間の端の 1 つに大きく傾いており、中央に近くない場合、何かが間違っている可能性もあります。

  • 分散。何百万もの値を生成した後、値空間の MIN と MAX に近い値が見られず、代わりに生成された値空間が狭い場合も、何か問題があります。

ついに。うまくいけば、適切な PRNG (たとえば AES に基づく) を使用しているため、提案された in situ-tests が代わりにエントロピー ソースに適用される可能性があります。

それが何らかの形で役立ったことを願っています。

于 2011-06-22T12:54:03.193 に答える
4

特定の数列が独立した同一分布 (iid) 確率変数である可能性を確認するために適用できる統計テストがあります。

George MarsagliaによるA Current View of Random Number Generatorsをご覧ください。特に、セクション 6 ～ 12 を見てください。これは、そのようなテストの概要を提供し、続いて適用できるいくつかのテストを提供します。

于 2011-06-22T10:19:41.560 に答える
2

確かに、乱数が実際にランダムであることを保証することはできません。
疑似乱数について：はい、それらはランダムに見えます（元々は暗号化で使用されていました）（疑似ランダム関数）、暗号化されたテキストとトラップ間の悪を送信すると、メッセージは彼が取得した暗号化されたテキストはランダムであると見なしますが、メッセージはいくつかの関数から計算されました。さらに、同じ関数とキーを使用して同じメッセージを取得します（存在する場合は、ランダムではありません。生成元の元のテキスト/番号を作成できないため、ランダムに見えます。 。ハッシュ関数（md5、sha1）や暗号化技術（des、aesなど）など。

于 2011-06-22T10:23:10.577 に答える
1

理論計算機科学は、コンピューターが決定論的機械であることを教えています。すべてのアルゴリズムは常に同じ方法で実行されるため、シードを変更する必要があります。しかし、コンピューターはどこからランダムシードを取得する必要がありますか？外部デバイスから？CPU温度（あまり変化しない）？

于 2011-06-22T10:22:17.333 に答える
1

数が乱数であるためには、それを予測できてはなりません。そのため、「乱数」を生成するアルゴリズムは疑似乱数を生成します。これは、以前に使用されたシードまたは「乱数化」中に使用された値を使用して、常に同じ一連の「乱数」数を生成できるためです。真の乱数は、たとえばサイコロを振ることで生成できますが、コンピューター アルゴリズムでは生成できません。

于 2011-06-22T10:15:34.943 に答える
-5

乱数を返す関数をテストするには、それを何度も呼び出して、各数値が何回返されるかを確認する必要があります。

例えば

For i := 1 to 1000000 do // Test the function 1.000.000 times
begin
   RandomNumber := Rand(9); // Random numbers from 0 to 9
   case RandomNumber of
      1 : Returned0 := Returned0 + 1;
      1 : Returned1 := Returned1 + 1;
      1 : Returned2 := Returned2 + 1;
      1 : Returned3 := Returned3 + 1;
      1 : Returned4 := Returned4 + 1;
      1 : Returned5 := Returned5 + 1;
      1 : Returned6 := Returned6 + 1;
      1 : Returned7 := Returned7 + 1;
      1 : Returned8 := Returned8 + 1;
      1 : Returned9 := Returned9 + 1;
   end;
end

WriteLn('0: ', Returned0);
WriteLn('1: ', Returned1);
WriteLn('2: ', Returned2);
WriteLn('3: ', Returned3);
WriteLn('4: ', Returned4);
WriteLn('5: ', Returned5);
WriteLn('6: ', Returned6);
WriteLn('7: ', Returned7);
WriteLn('8: ', Returned8);
WriteLn('9: ', Returned9);

完全な出力は、各ランダム出力の数値が等しい必要があります。何かのようなもの：

0: 100000
1: 100000
2: 100000
3: 100000
4: 100000
5: 100000
6: 100000
7: 100000
8: 100000
9: 100000
于 2011-06-22T10:30:11.817 に答える