Loading article…
疑似乱数列は、完全に決定論的で反復可能なプロセスによって生成されたにもかかわらず、統計的にランダムであるように見える数列です。 [1]疑似乱数ジェネレータは、人間が利用できる従来のランダム性のソース（サイコロを振るなど）がコンピュータープログラムで容易に利用できない物理的なプロセスに依存しているため、コンピュータープログラミングでよく使用されますが、ハードウェア乱数ジェネレータ技術の発達により、これに課題が生じています。
背景
乱数生成には、ランダムサンプリング、モンテカルロ法、ボードゲーム、ギャンブルなど、多くの用途があります。しかし物理学では、重力加速などのほとんどのプロセスは決定論的であり、同じ開始点から常に同じ結果を生成します。注目すべき例外は放射性崩壊と量子測定で、どちらも基礎となる物理学では真にランダムなプロセスとしてモデル化されています。これらのプロセスは乱数の実用的なソースではないため、決定論的なプロセスによって生成されるにもかかわらず、理想的には真にランダムなシーケンスの予測不可能性を持つ疑似乱数が使用されます。[2]
多くのアプリケーションでは、決定論的プロセスは疑似乱数ジェネレータと呼ばれるコンピュータアルゴリズムであり、最初にランダムシードと呼ばれる数値を提供する必要があります。同じシードは毎回同じシーケンスを生成するため、シードを適切に選択して隠しておくことが重要です。特に、パターンの予測不可能性は重要な機能であるセキュリティアプリケーションでは重要です。[3]
シーケンスが明らかに予測不可能であることが重要な場合、放射性崩壊、ラジオ局間でチューニングされた大気中の電磁ノイズ、またはキーストロークの混合タイミングなどの乱数の物理的な発生源が使用されてきました。[1] [4]これらの数値を取得するのに必要な時間の投資は、妥協につながります。つまり、これらの物理的な読み取り値の一部を疑似乱数ジェネレータのシードとして使用します。
歴史
現代のコンピュータが登場する以前は、乱数を必要とする研究者は、さまざまな手段（サイコロ、カード、ルーレットホイール、[5]など）で乱数を生成するか、既存の乱数表を使用していました。
研究者に乱数をすぐに提供しようとする最初の試みは1927年、ケンブリッジ大学出版局がLHCティペットが開発した41,600桁の表を出版したときでした。1947年にランド研究所はルーレットホイールの電子シミュレーションによって数字を生成しました。[5]その結果は最終的に1955年に「A Million Random Digits with 100,000 Normal Deviates」として出版されました。
計算の複雑さにおいて
理論計算機科学では、分布が特定のクラスの敵に対して疑似ランダムであるとは、そのクラスの敵が一様分布と有意な優位性をもって区別できない場合をいう。 [6]この疑似ランダム性の概念は計算複雑性理論 で研究されており、暗号学にも応用されている。
正式には、SとT を有限集合とし、F = { f : S → T } を関数のクラスとします。S上の分布 DがFに対してε疑似ランダムであるとは、 F内のすべてのfに対して、分布と（ はDからサンプリングされ、 はS上の一様分布からサンプリングされる）間の統計距離が最大で ε 以下である場合をいいます。
典型的な応用では、クラスF は限られたリソースを持つ計算モデルを記述し、Fに対して疑似ランダムな特定の特性を持つ分布D を設計することに関心があります。分布D は、疑似ランダムジェネレータの出力として指定されることが多いです。[7]
参照
- 暗号的に安全な疑似乱数生成器 – 根を求めるアルゴリズムでは解けないように設計された関数の種類
- 乱数ジェネレーターのリスト
- 疑似ランダムバイナリシーケンス – 決定論的アルゴリズムによって作成された、一見ランダムで予測が難しいビットストリーム
- 擬似ランダムアンサンブル
- 疑似乱数生成器 – 乱数列の近似値を生成するアルゴリズム
- 低矛盾シーケンス – 数学的シーケンスのタイプ
- 乱数生成 – ランダムな偶然よりも予測できないシーケンスを生成する
- 疑似ランダムノイズ – ノイズに似た特性を持つ疑似ランダム信号
さらに読む
- ドナルド・E・クヌース (1997) 『コンピュータプログラミングの技法』第2巻: 半数値アルゴリズム (第3版) Addison-Wesley Professional、ISBN 0-201-89684-2
- ゴールドライヒ、オデッド（2008）。計算の複雑さ：概念的視点。ケンブリッジ大学出版局。ISBN 978-0-521-88473-0。特に第8章「疑似乱数ジェネレータ」（284～348ページ）と付録C.2「疑似乱数性」（490～493ページ）を参照してください。
- Vadhan, SP (2012). 「疑似ランダム性」.理論計算機科学の基礎と動向. 7 (1–3): 1–336. doi :10.1561/0400000010.
外部リンク
- HotBits: 放射性崩壊によって生成された本物の乱数
- 暗号品質の乱数の使用と作成
- RFC 4086では、暗号における疑似乱数列の使用について詳細に議論されています。[8]
参考文献
- ^ ab ジョージ・ジョンソン (2001 年 6 月 12 日)。「混沌の専門家が価値ある製品、ランダム性を提供」ニューヨーク・タイムズ。
- ^ SP Vadhan (2012).疑似ランダム性。
疑似ランダム性とは、ランダム性をほとんどまたはまったく使用せずに構築されているにもかかわらず、「ランダムに見える」オブジェクトを効率的に生成する理論です。
- ^ Mark Ward (2015年8月9日). 「Webの乱数は弱すぎる、研究者が警告」BBC。
- ^ Jonathan Knudson (1998 年 1 月)。「Javatalk: 蹄鉄、手榴弾、乱数」。Sun Server。pp . 16–17。
- ^ ab 「A Million Random Digits」 RAND Corporation 2001年1月。 2017年3月30日閲覧。
- ^ Oded Goldreich. 計算の複雑さ：概念的観点。ケンブリッジ大学出版局。2008年。
- ^ 「疑似ランダム性」（PDF）。
- ^ D. Eastlake、3rd; J. Schiller; S. Crocker (2005 年 6 月)。セキュリティのためのランダム性要件。doi : 10.17487 /RFC4086。BCP 106。RFC 4086。 ベスト コモン プラクティス。RFC 1750 は 廃止されます。