導入
擬似乱数ジェネレーター( PRNG ) は、特定のランダムな特性を示す一連の数値を生成するアルゴリズムです。たとえば、数値は互いにほぼ独立していると想定されており、特定のルール (グループの動作) に従う数値のグループを特定するのは潜在的に困難です。
ただし、このようなジェネレーターの出力は完全にランダムではありません。完全にランダムなソースの理想的な特性にのみ近づくことができます。ジョン・フォン・ノイマンは、次の発言でこの事実を強調しました。「乱数を生成するための算術手法を考える人は、もちろん、罪を犯しています。」真の乱数は、特定の確率的物理的特性 (抵抗ノイズなど) を利用するハードウェアで生成できます。
擬似ランダムのレンダリングに満足している理由は、一方では「本物の」乱数を取得するのが難しく、特定の状況では本物のランダムの代わりに擬似的な数値ランダムを使用できるためです。数字。一方、これらは特にコンピュータ実装に適合したジェネレータであるため、より簡単かつ効率的に使用できます。
擬似ランダム手法は、コンピュータ上で、モンテカルロ法、シミュレーション、暗号アプリケーションなどのさまざまなタスクでよく使用されます。擬似ランダム発生器のランダム性の程度を決定するには、厳密な数学的分析が必要です。オークリッジ国立研究所のロバート R. コベユーは、「乱数生成は偶然に任せるにはあまりにも重要である」と記事で書いています。
ほとんどの擬似ランダム アルゴリズムは、均一に分散された出力を生成しようとします。非常に一般的なクラスのジェネレーターでは、線形合同が使用されます。他のものは、前の 2 つの値を加算することによってフィボナッチ数列からインスピレーションを得たり、前の結果が中間変換後に注入されるシフト レジスタを使用したりします。特定の擬似乱数生成器は、特定の制約が満たされる場合、暗号と呼ばれます。とりわけ、Fortuna、 Yarrow 、またはBlum Blum Shub を挙げてみましょう。
「擬似ランダム」という用語を説明する問題
アルゴリズムが何であるかを知っていても、アルゴリズムを使用して乱数を作成することは、非常に疑わしいように思えるかもしれません。さらに、ランダム性を適切に定義する方法がわからないことを考えると、アルゴリズムを使用してランダムなシーケンスを生成することさえできるのか疑問に思います。
これらの批判は完全に正当であり、否定することはできません。これらが、擬似乱数ジェネレーターについて話す理由です。実際には、アルゴリズム手法を使用して乱数を生成することによる悪影響を制限することが可能です。
使用される手法に固有のバイアス
乱数生成器は決定論的コンピューター上で実行されるため、事実上の決定論的アルゴリズムとなります。その出力は、真のランダム シーケンスには存在しない特性、つまり周期性によって必然的に汚染されます。リソース (メモリ、レジスタの数など) が限られている場合、ジェネレータは少なくとも 2 回同じ内部状態に戻ります。その後、必然的にサイクルに入ります。非周期ジェネレータは不可能ではありませんが、同じ状態に陥るのを避けるためにメモリを増やす必要があります。この理論的な障害を回避するために、ジェネレーターは任意の状態 (「シード」) で開始できます。ただし、シードが同一であれば同じ結果が得られます。これは、特定の条件下では、特に再現性の点で利点であると考えられます。さらに、可能なシードの数は無限ではなく、ジェネレーターは限られた数の異なるシーケンスしか生成できません。
出力の品質を向上させるために、たとえばハードディスクへの 2 回のアクセス間の時間や、コンピュータが起動してからのミリ秒数など、システムの不完全性から生じる「ランダムな」コンポーネントを導入できます。ただし、これらの値は特定の間隔の間にある、および/または部分的に予測可能です。システムは擬似ランダムのままです。
完璧なチャンスからの逸脱
内部状態にビットが追加されるたびに、最大期間長は2 倍になります。コンピュータが計算できるよりも長い周期を持つ擬似乱数発生器を構築するのは簡単です。 Mersenne Twister は、非暗号アプリケーション向けの優れた乱数生成器であり、周期が2 19937 − 1という天文学的な数であることが数学的に証明されています。
アルゴリズムによって生成された擬似乱数シーケンスを、生成元のシードを知らずに完全な乱数源から区別できるかどうかについては、まだ疑問が残っています。暗号化の分野では、ほとんどの専門家は、これは現在の計算能力では不可能であると考えています。この原理は、疑似ランダム シーケンスとデータの間で XOR を実行する RC4 のようなストリーム暗号に使用されます。
原則として、ほとんどのジェネレーターには、統計分析で明らかにできる数学的問題があります。多くの場合、出力品質は生成速度を犠牲にして向上するため、ジェネレーターを使用する場合はこれらのパラメーターを考慮する必要があります。欠陥としては次のようなものが考えられます。
- 種によっては期間が短くなる
- 発電機の品質は種子によって大きく異なります
- 不完全な分布、均一性の欠如
- 1 より大きい次元の空間での悪い分布
- またはその逆: 分布が理想的すぎる、均一性が完璧すぎる
- 独立していない連続する値 (ランダムなソースから生成ステップにデータを注入しない限り、これは常に当てはまります)
- 出力の一部のビットはランダム性が低くなります (たとえば、ビット #8 は多くの場合 1 のままです)
欠陥は重大な場合もあれば、ほとんど見えない場合もあります。数十年間使用されてきたRANDUアルゴリズムには偏りがあり、当時得られた結果の中には完全に検証できないものもあります。場合によっては、実際のアプリケーションで問題が明らかになることがあります (たとえば、完全に予期しない結果が得られた物理シミュレーションなど) が、問題を把握するために、使用前にいくつかのテストを行うことが最善です。
