擬似乱数発生器

擬似乱数発生器（PRNG ）は、決定論的乱数ビット発生器（DRBG ）とも呼ばれ、^{[ 1 ]}乱数列の特性に近似する特性を持つ数列を生成するアルゴリズムです。PRNG によって生成される数列は、PRNG のシードと呼ばれる初期値（真の乱数値を含む場合もある）によって完全に決定されるため、真の乱数ではありません。ハードウェア乱数発生器を使用すれば、真の乱数に近い数列を生成できますが、擬似乱数発生器は、乱数生成の速度と再現性の高さから、実際には重要です。^{[ 2 ]}

擬似乱数生成器（PRNG）は、シミュレーション（モンテカルロ法など）、電子ゲーム（プロシージャル生成など）、暗号化といったアプリケーションにおいて中心的な役割を果たします。暗号化アプリケーションでは、出力が以前の出力から予測できないことが求められるため、より単純なPRNGの線形性を継承しない、より高度なアルゴリズムが必要となります。

良好な統計的特性は、擬似乱数発生器の出力にとって中心的な要件です。一般的に、擬似乱数発生器が意図した用途に適した、十分にランダムに近い数値を生成するという確信を持つためには、慎重な数学的分析が必要です。ジョン・フォン・ノイマンは、擬似乱数発生器を真の乱数発生器と誤解することについて警告し、「乱数を生成する算術的方法を考える人は、もちろん罪深い状態にある」と冗談を言いました。^{[ 3 ]}

実際には、多くの一般的な擬似乱数生成器の出力には、統計的パターン検出テストに失敗する原因となるアーティファクトが見られます。これには以下が含まれます。

• 一部のシード状態（この文脈では「弱い」シード状態と呼ばれることがある）については、予想よりも短い期間で済む。
• 大量の生成数値の分布に均一性が欠けている。
• 連続する値の相関関係。
• 出力シーケンスの次元分布が不良である。
• 特定の値が発生する場所間の距離は、ランダムなシーケンス分布における距離とは異なる分布を示す。

欠陥のある擬似乱数生成器（PRNG）に見られる不具合は、気づかれない（そして知られていない）ものから、非常に明白なものまで多岐にわたる。例えば、メインフレームコンピュータで数十年にわたって使用されてきたRANDU乱数生成アルゴリズムが挙げられる。これは深刻な欠陥を抱えていたが、その不備は長い間見過ごされていた。

多くの分野では、21世紀以前の研究はランダム選択やモンテカルロシミュレーションに依存していたり​​、その他の方法で擬似乱数生成器（PRNG）に依存していたり​​したが、質の低いPRNGを使用していたため、理想よりもはるかに信頼性が低かった。^{[ 4 ]}今日でも、国際統計科学百科事典（2010年）の次の警告が示すように、注意が必要な場合がある。 ^{[ 5 ]}

広く使われている乱数生成器のうち、使用をやめるべきものは、優れた乱数生成器よりもはるかに多い。ソフトウェアベンダーを盲目的に信用してはいけない。お気に入りのソフトウェアのデフォルトの乱数生成器を確認し、必要に応じて交換できるように準備しておこう。この最後の推奨事項は、過去40年間、何度も繰り返し述べられてきた。驚くべきことに、それは40年前と変わらず、今日でもなお重要である。

例として、広く使われているプログラミング言語Javaを考えてみましょう。2020 年までは、Java は擬似乱数生成器 (PRNG) に線形合同法生成器(LCG) を使用していましたが、^{[ 6 ] [ 7 ]}これは品質が低いものでした (後述)。Java 17で Java のサポートがアップグレードされました。

大きな問題を回避しつつ、比較的高速に動作する有名な擬似乱数生成器（PRNG）の一つに、1998年に発表されたメルセンヌ・ツイスター（後述）があります。計算性能と統計性能の両面でより高品質なPRNGは、この日付の前後に開発されており、擬似乱数生成器の一覧で確認できます。

20世紀後半、擬似乱数生成器（PRNG）に使用される標準的なアルゴリズムは、線形合同法生成器（LCG）で構成されていた。LCGの品質は不十分であることが知られていたが、より良い方法は利用できなかった。Pressら （2007）は、その結果を次のように説明している。「LCGや関連するアルゴリズムのために結果に疑問があるすべての科学論文が図書館の棚から消えたとしたら、各棚には拳ほどの大きさの隙間ができるだろう。」^{[ 8 ]}

擬似乱数発生器の構築における大きな進歩は、2要素体上の線形漸化式に基づく技術の導入であり、このような発生器は線形フィードバックシフトレジスタに関連している。

特に、1997年に発明されたメルセンヌ・ツイスター[ ^{9 ]は、以前のジェネレーターの多くの問題を回避した。メルセンヌ・ツイスターの周期は2¹⁹⁹³⁷} − 1回の反復（≈ 4.3 × 10⁶）^{である。    6001} ) は、（最大）623 次元（32 ビット値の場合）で均等に分布することが証明されており、導入当時は他の統計的に妥当なジェネレータよりも高速に動作していました。

2003年、ジョージ・マルサグリアは、線形再帰に基づくxorshiftジェネレータのファミリーを導入しました^{[ 10 ]}。このようなジェネレータは非常に高速で、非線形演算と組み合わせることで強力な統計的テストに合格します^{[ 11 ] [ 12 ] [ 13 ] 。}

2006年にWELLファミリーのジェネレータが開発されました。^{[ 14 ]} WELLジェネレータは、状態空間が大きすぎ、ゼロの数が多い状態空間からの回復が非常に遅いメルセンヌツイスターの品質をある程度改善しています。

カウンタベース乱数生成器（CBRNG、カウンタベース擬似乱数生成器、またはCBPRNGとも呼ばれる）は、内部状態として整数カウンタのみを使用する擬似乱数生成器の一種である。

$${\displaystyle {\text{出力}}=f(n,{\text{キー}})}$$

これらは一般的に、GPUやCPUクラスタなどの大規模並列計算用の擬似乱数を生成するために使用されます。^{[ 15 ]}それらにはいくつかの利点があります。

• 必要な「状態」はカウンタ値とキーのみです。特定のカウンタとキーに対して、出力は常に同じになります。この特性により、CBRNGは再現性を持ちます。
• 各乱数は以前の出力とは独立して計算されるため、並列処理で生成できます。例えば、大規模並列アプリケーションでは、各スレッドまたはGPUコアにカウンタ値の範囲を割り当て、同期や状態共有なしに乱数を計算できます。
• ジェネレーターはすべての中間状態を経由する必要がないため、一定時間でシーケンス内の任意のポイントに「ジャンプ」できます。これは、独立したストリームが必要となるモンテカルロシミュレーションなどのアプリケーションで特に役立ちます。

例としては、次のものが挙げられます。^{[ 15 ]}

• Philox：乗算に基づく混合方式を用いて、カウンターとキーを組み合わせます。
• Threefry： Threefishブロック暗号の強度を弱めたバージョンに基づいています。

暗号アプリケーションに適した擬似乱数生成器は、暗号的に安全な擬似乱数生成器（CSPRNG）と呼ばれます。CSPRNGの要件は、シードを知らない攻撃者が、生成器の出力シーケンスをランダムなシーケンスと区別する際に、ほとんど利点がないことです。言い換えれば、擬似乱数生成器は特定の統計的テストに合格するだけでよいのに対し、CSPRNGはシードのサイズに関して多項式時間に制限されたすべての統計的テストに合格する必要があります。この特性の証明は、現在の計算複雑性理論の最先端を超えていますが、整数因数分解などの難しいと想定される問題をCSPRNGに還元することで、強力な証拠が得られる可能性があります。^{[ 16 ]}一般に、アルゴリズムがCSPRNGとして認定されるまでには、何年もの審査が必要になる場合があります。

CSPRNGには以下のような種類があります。

• ストリーム暗号
• カウンター^{[ 17 ]}または出力フィードバックモードで動作するブロック暗号
• 暗号学的に安全になるように特別に設計された擬似乱数生成器（PRNG）には、Microsoftの暗号化アプリケーションプログラミングインターフェイス関数CryptGenRandom、Yarrow アルゴリズム（Mac OS XおよびFreeBSDに組み込まれている）、およびFortunaなどがあります。
• 複数の擬似乱数生成器（PRNG）の基本アルゴリズムを組み合わせて、検出可能な非ランダム性を排除しようとする組み合わせPRNG。
• 数学的困難性の仮定に基づく特別な設計:例としては、Micali–Schnorrジェネレータ、^{[ 18 ]} Naor-Reingold擬似乱数関数、およびBlum Blum Shubアルゴリズムがあり、これらは強力なセキュリティ証明を提供します (このようなアルゴリズムは従来の構成に比べてかなり遅く、多くのアプリケーションには実用的ではありません)。
• 汎用的な擬似乱数生成器: （暗号学的に）安全な擬似乱数生成器は任意の一方向関数から汎用的に構築できることが示されているが、^{[ 19 ]}この汎用的な構築は実際には非常に遅いため、主に理論的な関心事である。

NSAがNIST認定の擬似乱数発生器Dual_EC_DRBGに非対称バックドアを挿入した可能性が高いことが示されている。^{[ 20 ]}

ほとんどの PRNG アルゴリズムは、いくつかのテストのいずれかによって均一に分布するシーケンスを生成します。高品質の PRNG の出力と真のランダム シーケンスを区別する方法があるかどうかは、暗号理論と実践の中心となる未解決の問題です。この設定では、識別者は、既知の PRNG アルゴリズムが使用された (ただし、初期化された状態は知らない) か、真のランダム アルゴリズムが使用されたかを知っており、その 2 つを区別する必要があります。^{[ 21 ]} PRNG を使用するほとんどの暗号アルゴリズムとプロトコルのセキュリティは、適切な PRNG の使用と真のランダム シーケンスの使用を区別することが不可能であるという仮定に基づいています。この依存関係の最も単純な例はストリーム暗号で、これは (ほとんどの場合)メッセージの平文と PRNG の出力を排他的 OR演算して暗号文を生成します。暗号的に適切な PRNG の設計は、追加の基準を満たす必要があるため、非常に困難です。周期の長さは擬似乱数発生器の暗号学的適合性において重要な要素ではあるが、唯一の要素ではない。

ドイツ連邦情報セキュリティ庁（ドイツ語：Bundesamt für Sicherheit in der Informationstechnik、BSI）は、決定論的乱数発生器の品質に関する4つの基準を定めています。^{[ 22 ]}以下にそれらを要約します。

• K1 – 生成された乱数列は互いに異なる可能性が高い。
• K2 – 指定された統計的検定によれば、数値のシーケンスは「真にランダムな」数値と区別できない。これらの検定は、モノビット検定（シーケンス内の 1 と 0 の数が等しいかどうか）、ポーカー検定（カイ二乗検定の特殊な場合）、ラン検定（さまざまな長さのランの頻度をカウント）、ロングラン検定（シーケンスの 20,000 ビット内に長さ 34 以上の長さのランが存在するかどうかをチェック）— は、BSI ^{[ 22 ]}とNIST ^{[ 23 ]}の両方から、および自己相関検定である。本質的に、これらの要件は、ビット シーケンスが次の条件をどの程度満たしているかをテストするものである。すなわち、0 と 1 が等しい頻度で含まれていること、 n個のゼロ（または 1）のシーケンスの後、次のビットが 1/2 の確率で 1（または 0）であること、および選択された任意のサブシーケンスがシーケンス内の次の要素に関する情報を一切含まないこと。
• K3 – 攻撃者が（実際的な目的において）任意の部分シーケンスから、シーケンス内の過去または未来の値、あるいはジェネレータの内部状態を計算したり推測したりすることは不可能であるべきである。
• K4 – 攻撃者が、ジェネレータの内部状態から、シーケンス内の以前の数値や以前の内部ジェネレータ状態を計算したり推測したりすることは、実際上不可能であるべきである。

暗号化アプリケーションにおいては、K3またはK4規格を満たすジェネレータのみが許容される。

与えられた条件:

• ${\displaystyle P}$– 確率分布${\displaystyle \left(\mathbb {R} ,{\mathfrak {B}}\right)}$（どこ${\displaystyle {\mathfrak {B}}}$（これは実数直線のすべてのボレル部分集合のシグマ代数である）
• ${\displaystyle {\mathfrak {F}}}$– ボレル集合の空でない集合${\displaystyle {\mathfrak {F}}\subseteq {\mathfrak {B}}}$例えば${\displaystyle {\mathfrak {F}}=\left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$。 もし${\displaystyle {\mathfrak {F}}}$指定されていないので、${\displaystyle {\mathfrak {B}}}$または${\displaystyle \left\{\left(-\infty ,t\right]:t\in \mathbb {R} \right\}}$文脈によります。
• ${\displaystyle A\subseteq \mathbb {R} }$– 空でない集合（必ずしもボレル集合とは限らない）。${\displaystyle A}$は、${\displaystyle P}$の支持部とその内部。例えば、${\displaystyle P}$区間上の一様分布${\displaystyle \left(0,1\right]}$、${\displaystyle A}$かもしれない${\displaystyle \left(0,1\right]}$。 もし${\displaystyle A}$が指定されていないため、サポートに含まれる何らかのセットであると想定されます。${\displaystyle P}$文脈によっては、その内部を含む場合もある。

関数を${\displaystyle f:\mathbb {N} _{1}\rightarrow \mathbb {R} }$（どこ${\displaystyle \mathbb {N} _{1}=\left\{1,2,3,\dots \right\}}$は正の整数の集合です）擬似乱数生成器${\displaystyle P}$与えられた${\displaystyle {\mathfrak {F}}}$値を取る${\displaystyle A}$の場合に限り：

• ${\displaystyle f\left(\mathbb {N} _{1}\right)\subseteq A}$
• $\displaystyle \forall E\in {\mathfrak {F}}\quad \forall \varepsilon >0\quad \exists N\in \mathbb {N} _{1}\quad \forall n\geq N,\quad \left|{\frac {\#\left\{i\in \left\{1,2,\dots ,n\right\}:f(i)\in E\right\}}{n}}-P(E)\right|<\varepsilon }$

（${\displaystyle \#S}$有限集合内の要素数を表す${\displaystyle S}$）

もし${\displaystyle f}$は、一様分布の擬似乱数発生器です。${\displaystyle \left(0,1\right)}$そしてもし${\displaystyle F}$ある確率分布の累積分布関数（CDF）は、${\displaystyle P}$、 それから${\displaystyle F^{*}\circ f}$は擬似乱数発生器です${\displaystyle P}$、 どこ${\displaystyle F^{*}:\left(0,1\right)\rightarrow \mathbb {R} }$パーセンタイルは${\displaystyle P}$つまり${\displaystyle F^{*}(x):=\inf \left\{t\in \mathbb {R} :x\leq F(t)\right\}}$直感的に言えば、任意の分布は標準一様分布のシミュレーションからシミュレーションできる。

1946年にジョン・フォン・ノイマンが提案した初期のコンピュータベースの擬似乱数生成器は、ミドルスクエア法として知られています。アルゴリズムは次のとおりです。任意の数値を2乗し、その結果の数値の中央の桁を「乱数」として取り除き、その数値を次の反復のシードとして使用します。たとえば、「1111」という数値を2乗すると「1234321」となり、これは「01234321」と表記できます。これは、4桁の数値を2乗すると8桁の数値になることを示しています。これにより、「2343」が「乱数」として得られます。この手順を繰り返すと、次の結果として「4896」が得られ、以下同様です。フォン・ノイマンは10桁の数値を使用しましたが、プロセスは同じでした。

「中央の正方形」方式の問題点は、すべての数列が最終的に繰り返されることであり、中には「0000」のように非常に速い繰り返しとなるものもある。フォン・ノイマンはこのことを認識していたが、この方法は自身の目的には十分であると考え、数学的な「修正」によって誤りが取り除かれるのではなく、単に隠蔽されるだけになるのではないかと懸念していた。

フォン・ノイマンは、ハードウェア乱数発生器は不適切だと判断した。なぜなら、生成された出力を記録しなければ、後でエラーをテストすることができないからである。出力を記録すると、当時利用可能だった限られたコンピュータのメモリを使い果たし、コンピュータの数値の読み書き能力も低下してしまう。数値をカードに書き込むと、書き込みと読み出しに非常に長い時間がかかる。彼が使用していたENIACコンピュータでは、「中央の正方形」方式によって、パンチカードから数値を読み込むよりも約100倍速い速度で数値を生成することができた。

中盤正方形法はその後、より精巧な生成器に取って代わられた。

最近の革新的な手法として、ミドルスクエアとワイルシーケンスを組み合わせる方法がある。この方法は長期間にわたって高品質な出力を生成する（ミドルスクエア法を参照）。

一様分布ではない確率分布から選択された数値は、一様分布の擬似乱数生成器と、2つの分布を関連付ける関数を用いて生成することができる。

まず、累積分布関数が必要となる。${\displaystyle F(b)}$目標分布の${\displaystyle f(b)}$:

${\displaystyle F(b)=\int _{-\infty }^{b}f(b')\,db'}$

ご了承ください${\displaystyle 0=F(-\infty )\leq F(b)\leq F(\infty )=1}$一様分布からの乱数cを「通過」する確率密度として使用すると、次のようになります。

${\displaystyle F(b)=c}$

となることによって

${\displaystyle b=F^{-1}(c)}$

分布からランダムに選択された数値${\displaystyle f(b)}$これは逆変換サンプリングに基づいています。

例えば、累積ガウス分布の逆数$\displaystyle \operatorname {erf} ^{-1}(x)}$入力として範囲(0, 1)の理想的な一様乱数発生器を使用する${\displaystyle x}$ガウス分布に従う（正の値のみの）値のシーケンスを生成するが、

• 実用的な数値表現を用いる場合、分布の無限に続く「裾野」を有限の値に切り捨てる必要がある。
• 繰り返し再計算$\displaystyle \operatorname {erf} ^{-1}(x)}$より高速な生成のためには、ジッグラトアルゴリズムなどの手段を用いて削減すべきである。

レイリー分布やポアソン分布などの他の非一様分布を生成する場合にも、同様の考慮事項が適用されます。

• Barker E.、Kelsey J.、「決定論的乱数ビット生成器を用いた乱数生成に関する推奨事項」、NIST SP800-90A、2012年1月
• Brent RP、「シフトとXORを用いたいくつかの長周期乱数発生器」、ANZIAM Journal、2007; 48:C188–C202
• Gentle JE (2003)、乱数生成とモンテカルロ法、Springer。
• Hörmann W.、Leydold J.、Derflinger G. (2004、2011)、Automatic Nonuniform Random Variate Generation、Springer-Verlag。
• Knuth DE 『コンピュータプログラミングの技法』第2巻：半数値アルゴリズム、第3版。Addison-Wesley、1997年。ISBN 0-201-89684-2第3章 [非ランダム性に関する統計的検定について詳細に解説。]
• Luby M.、『擬似乱数と暗号応用』、プリンストン大学出版局、1996年。ISBN 9780691025469
• von Neumann J.、「乱数に関連して使用されるさまざまな手法」、AS Householder、GE Forsythe、およびHH Germond編、『モンテカルロ法』、米国標準局応用数学シリーズ、12（ワシントンDC：米国政府印刷局、1951年）：36-38。
• ピーターソン、アイヴァース（1997）。ランダム性のジャングル ：数学のサファリ。ニューヨーク：ジョン・ワイリー＆サンズ。ISBN 0-471-16449-6。
• Press WH、Teukolsky SA、Vetterling WT、Flannery BP (2007)、Numerical Recipes ( Cambridge University Press )。
• Viega J.、「ソフトウェアにおける実用的な乱数生成」、第19回コンピュータセキュリティアプリケーション会議議事録、2003年12月。

• TestU01：無料の最新鋭（GPLライセンス）C++乱数テストスイート。
• DieHarder：無料の（GPLライセンス）C言語乱数テストスイート。
• 「乱数の生成」（組み込みシステムにおける）エリック・ウナー著（2004年）
• 「Linux乱数発生器の分析」Zvi Gutterman、Benny Pinkas、Tzachy Reinman著（2006年）
• 「より優れた擬似乱数生成器」、Parikshit Gopalan、Raghu Meka、Omer Reingold、Luca Trevisan、Salil Vadhan著( Microsoft Research、2012)
• Rand() 関数がYouTube上で有害とみなされる（Stephan Lavavej 著、Microsoft、2013 年）
• Wsphynxはシンプルなオンライン乱数生成器です。乱数はJavaScriptの擬似乱数生成器（PRNG）アルゴリズムによって生成されます。