Loading article…
擬似乱数列とは、完全に決定論的で再現可能なプロセスによって生成されたにもかかわらず、統計的にランダムに見える数列のことです。 [ 1 ]擬似乱数発生器は、コンピュータ プログラムでよく使用されます。これは、人間が利用できる従来のランダム性の発生源（サイコロを振るなど）が、コンピュータ プログラムでは容易に利用できない物理的プロセスに依存しているためですが、ハードウェア乱数発生器技術の発展により、この状況は変わりつつあります。
乱数の生成には、ランダムサンプリング、モンテカルロ法、ボードゲーム、ギャンブルなど、多くの用途があります。しかし、物理学では、重力加速度などのほとんどのプロセスは決定論的であり、同じ開始点から常に同じ結果を生み出します。注目すべき例外として、放射性崩壊と量子測定があり、これらはどちらも基礎となる物理学において真にランダムなプロセスとしてモデル化されています。これらのプロセスは実用的な乱数源ではないため、擬似乱数が使用されます。擬似乱数は、決定論的なプロセスによって生成されるにもかかわらず、理想的には真のランダムな数列の予測不可能性を持っています。[ 2 ]
多くのアプリケーションでは、決定論的なプロセスは擬似乱数発生器と呼ばれるコンピュータアルゴリズムであり、まず乱数シードと呼ばれる数値を与える必要があります。同じシードは毎回同じシーケンスを生成するため、特にパターンの予測不可能性が重要な特徴となるセキュリティアプリケーションでは、シードを適切に選択し、隠しておくことが重要です。 [ 3 ]
シーケンスが明らかに予測不可能であることが重要な場合、放射性崩壊、局間で同調したラジオから収集した大気電磁ノイズ、またはキーストロークのタイミングの混在など、乱数の物理的な発生源が使用されてきました。[ 1 ] [ 4 ]これらの数値を取得するのに必要な時間投資により、妥協案として、これらの物理的測定値の一部を擬似乱数発生器のシードとして使用することになります。
現代のコンピューティングが登場する以前は、乱数を必要とする研究者は、さまざまな方法（サイコロ、カード、ルーレットホイール[ 5 ]など）で乱数を生成するか、既存の乱数表を使用していました。
研究者に乱数をすぐに提供しようとする最初の試みは1927年に行われ、ケンブリッジ大学出版局がLHCティペットによって開発された41,600桁の表を出版した。1947年には、ランド研究所がルーレットホイールの電子シミュレーションによって数値を生成した[ 5 ] 。その結果は最終的に1955年に「100,000個の正規偏差を持つ100万個の乱数」として出版された。
理論計算機科学では、あるクラスの敵対者がその分布を一様分布と有意な利点をもって区別できない場合、その分布は、あるクラスの敵対者に対して擬似ランダムであると言えます。 [ 6 ] この擬似ランダム性の概念は、計算複雑性理論で研究されており、暗号学に応用されています。
形式的には、SとT を有限集合とし、F = { f : S → T } を関数のクラスとする。S上の分布Dは、 Fのすべてのfに対して、分布間の統計的距離がε-擬似ランダムである場合に、 Fに対してε-擬似ランダムである。そして、 どこDからサンプリングされ、はS上の一様分布からサンプリングされ、最大で ε です。
典型的なアプリケーションでは、クラスF は制限されたリソースを持つ計算モデルを表し、Fに対して擬似乱数となる特定の特性を持つ分布Dを設計することに関心があります。分布D は、擬似乱数生成器の出力として指定されることがよくあります。[ 7 ]
擬似乱数とは、ほとんどまたは全く乱数を用いずに構築されているにもかかわらず、「ランダムに見える」オブジェクトを効率的に生成する理論である。
