ステートレス乱数ジェネレーターは存在しますか？

Question

単一の乱数ジェネレーター（RNG）を使用して複数の数値を生成することと、ジェネレーターごとに1つの数値を生成して破棄することには違いがありますか？両方の実装は、等しくランダムな数値を生成しますか？このために通常のRNGとセキュアRNGに違いはありますか？

クライアントに代わって乱数のリストを生成することになっているWebアプリケーションがあります。つまり、数値は各クライアントの観点からランダムに見える必要があります。これは、クライアントセッションごとに個別のランダムRNGを保持する必要があるということですか？または、すべてのセッションで単一のRNGを共有できますか？または、リクエストごとにRNGを作成および破棄できますか？

更新：この質問は、ランダムシーケンスのサブセットもランダムですか？

Answer 1

乱数ジェネレーターには状態があります。これは実際に必要な機能です。次の「ランダム」番号は、以前の番号とシード/状態の関数です。純粋主義者はそれらを擬似乱数ジェネレーターと呼びます。数値はランダム性の統計的検定に合格しますが、実際にはランダムではありません。

乱数値のシーケンスは有限であり、繰り返します。

乱数の生成を、数字のコレクションをシャッフルしてから、ランダムな順序で処理すると考えてください。シードは「シャッフル」に使用されます。数字。シードが設定されると、数値のシーケンスは固定され、予測が非常に困難になります。一部のシードは他のシードよりも早く繰り返されます。

ほとんどのジェネレーターは、誰もそれを繰り返すことに気付かないほど長い期間を持っています。 48ビットの乱数ジェネレーターは、繰り返す前に数千億の乱数を生成します（32ビットのシード値を使用して）。

単一のシードを与えて値を吐き出させると、ジェネレーターはランダムな値をのみ生成します。シードを変更した場合、新しいシード値で生成された数値は、前のシードで生成された値と比較するとランダムに表示されない場合があります。シードを変更すると、すべてのベットがオフになります。しないでください。

健全なアプローチは、1つのジェネレーターと「取引」を行うことです。さまざまなクライアントの周りの数字。ジェネレーターの作成と破棄を台無しにしないでください。種の変更を台無しにしないでください。

何よりも、独自の乱数ジェネレーターを作成しないでください。ほとんどの言語ライブラリの組み込みジェネレーターは本当に優れています。特に32ビット以上を使用する最新のもの。

一部のLinuxディストリビューションには、 / dev / random および / dev / urandom デバイスがあります。これらを一度読んで、アプリケーションの乱数ジェネレーターをシードできます。これらは多かれ少なかれランダムな値を持っていますが、「ノイズを収集する」ことで機能します。ランダムシステムイベントから。それらを控えめに使用して、使用の間に多くのランダムなイベントがあるようにしてください。

Answer 2

単一のジェネレーターを複数回使用することをお勧めします。私の知る限り、すべてのジェネレーターには状態があります。ジェネレータをシードするとき、その状態をシードに基づいて設定します。新しいものを生成し続ける場合、選択するシードは、1つのジェネレーターを使用して生成される数ほどランダムではない可能性があります。

これは、私が使用したほとんどのジェネレーターで特に当てはまり、現在の時間をミリ秒単位でシードとして使用します。

Answer 3

ハードウェアベースの真の[1]乱数ジェネレーターは可能ですが、自明ではなく、平均レートが低いことがよくあります。可用性も問題になる可能性があります[2]。 「ショットノイズ」のグーグル検索または「放射性崩壊」 「乱数ジェネレータ」と組み合わせていくつかのヒットを返すはずです。

これらのシステムは状態を維持する必要はありません。おそらくあなたが探していたものではありません。

他の人が述べたように、ソフトウェアシステムは擬似ランダムであり、状態を維持する必要があります。

妥協案は、ハードウェアベースのRNGを使用して、PRNGのシードに使用できるエントロピープール（保存状態）を提供することです。これは、/ dev / random [3]および/ dev / urandom [4]のLinux実装で非常に明示的に行われます。

これらは、/ dev / randomエントロピープールへのデフォルト入力が実際にどれだけランダムであるかについての引数です。

---

脚注：

1. 物理学の理解に関する問題を修正する
2. ランダムなプロセスを待っているため
3. / dev / random機能は、実際にまたはほぼランダムであると考えられるさまざまなソースからシードされたエントロピープールに直接アクセスし、エントロピーが使い果たされるとブロックします
4. / dev / urandomは/ dev / randomに似ていますが、エントピーが使い果たされると暗号化ハッシュが使用され、エントロピープールが事実上ステートフルPRNGになります

Answer 4

RNGを作成し、そこから単一の乱数を生成し、RNGを破棄した場合、生成される数値は、RNGの起動に使用されるシードと同じくらいランダムです。

単一のRNGを作成し、そこから多くの数値を引き出す方がはるかに良いでしょう。

Answer 5

すでに述べたように、PRNGを一度シードしてから再利用する方がずっと良いです。安全なPRNGは、暗号化アプリケーションに適したものです。毎回再播種することで合理的にランダムな結果が得られる唯一の方法は、真にランダムな「実世界」から来る場合です。ソース-特殊なハードウェア。その場合でも、ソースにバイアスがかかっている可能性があり、理論的には同じPRNGを使用する方が優れています。

Answer 6

通常、深刻なPRNGには新しい状態をシードするのにかなり時間がかかり、毎回新しい状態を作成してもあまり役に立ちません。 複数のPRNGが必要な場合は、カードをシャッフルするためのジェネレーターが1つ、コンピューター制御キャラクターによって行われるコメントを生成するためのジェネレーターが1つあるなど、本当に専用のジェネレーターが必要です。ユーザーはキャラクターの行動に基づいて結果を推測することはできません。

シードの良い解決策は、 this（Random.org）を使用することです。無料で大気ノイズから生成された数値。時間を使用するよりもシードの良いソースになる可能性があります。

編集：良いプログラミング標準以外の理由がない限り、クライアントごとに1つのPRNGを間違いなく使用します。とにかく、クライアント間で1つのPRNGを共有する場合、PRNGの品質に等しい品質の疑似乱数値をそれぞれに提供します。したがって、これは実行可能なオプションですが、プログラミングには不適切なポリシーのようです

Answer 7

Haskellは可変状態を完全に排除しようとする言語であることに言及する価値があります。 IO（何らかの形式の可変性を必要とする）のようなハード要件とこの目標を調整するには、ある計算から次の計算に状態をスレッド化するためにモナドを使用する必要があります。このようにして、Haskellは疑似乱数ジェネレーターを実装します。厳密に言えば、乱数の生成は本質的にステートフルな操作ですが、Haskellは状態「突然変異」を移動することでこの事実を隠すことができます。バインド（＆gt;＆gt; = ）操作に追加します。

これはおそらく少し抽象的に聞こえますが、実際にはあなたの質問に完全に答えているわけではありませんが、まだ適用できると思います。理論的な観点からは、状態に関与せずにRNGを操作することは不可能です。とにかく、この相互作用を軽減し、操作全体がステートレスな性質であるかのように表示するために使用できる手法があります。

Answer 8

通常、単一のPRNGを作成し、そこから複数の値を取得する方が適切です。複数のインスタンスを作成すると、インスタンスのシードが一意であることが保証されるようにする必要があり、インスタンス固有の情報を組み込む必要があります。

余談ですが、より良い＆quot; true＆quot;があります。乱数ジェネレーターですが、通常、コンピューター内部の電気信号の分散からランダムデータを引き出すなどのことを行う特殊なハードウェアが必要です。本当に心配しない限り、シード値が簡単に予測できない限り、言語ライブラリやOSに組み込まれた疑似乱数ジェネレーターでおそらく十分でしょう。

Answer 9

安全なPRNGの使用は、アプリケーションによって異なります。乱数は何に使用されますか？ それらが本当の価値のあるもの（例えば、暗号的に関連するもの）であれば、それ以下のものは使いたくないでしょう。

安全なPRNGははるかに低速であり、任意の精度の操作や素数テストなどを行うにはライブラリが必要になる場合があります...

Answer 10

まあ、それらが作成されるたびに異なってシードされる限り、いいえ、違いはないと思います。ただし、時間のようなものに依存している場合、シードが偏っているため、おそらく不均一になります。