擬似乱数生成器の原理（PRNG）

擬似乱数は「決定的な数列」である

コンピュータの random() が返す値は、物理的なノイズから取った真の乱数ではなく、初期値さえ決まれば完全に再現できる決定的な数列です。擬似乱数生成器（PRNG）は、内部に有限ビットの状態（state）を持ち、毎回その状態を漸化式で更新し、状態の一部を加工して出力する有限状態機械にすぎません。最初の状態を決める値を**シード（seed）**と呼び、同じシードを与えれば、同じプラットフォームで同じ数列が必ず再現されます。

この「再現できる」性質は欠点ではなく機能です。シミュレーションのデバッグ、テストの再現、プロパティベーステストの反例の再生は、すべてシード固定の決定性に支えられています。一方で、状態が有限ビットである以上、数列は必ずどこかで循環します。状態がwビットなら取りうる状態は最大で2のw乗通りなので、**周期（period）**の上限も2のw乗です。良いPRNGとは「周期が長く、出力が統計的に乱数らしく、必要な速度で回る」ものを指し、用途ごとに重視点が変わります。

線形合同法（LCG） — 最古にして最速、しかし脆い

最も古典的なPRNGが**線形合同法（Linear Congruential Generator, LCG）**です。漸化式はたった一行です。

// X_{n+1} = (a * X_n + c) mod m
uint32_t lcg(uint64_t *state) {
    *state = (6364136223846793005ULL * (*state) + 1442695040888963407ULL);
    return *state >> 33;   // 上位ビットだけを出力に使う
}

乗数 a、増分 c、法 m を適切に選ぶと（Hull–Dobellの条件を満たすと）周期は最大の m になります。乗算と加算だけで状態を1ワード持てばよく、極めて高速・省メモリで、多くの言語の素朴な rand() の実体でもあります。

しかしLCGには構造的な弱点があります。第一に、m が2のべき乗のとき下位ビットほど周期が短いことです。最下位ビットは0と1を交互に繰り返すだけ、というように、低位ビットの乱数性は壊滅的に悪くなります。そのため上のコードのように上位ビットだけを取り出すのが鉄則です。第二に、生成した値を組（k次元の点）として並べると、それらが少数の超平面（格子）上に整列してしまう「Marsagliaの定理」の問題があります。古典的なRANDU（a=65539）はこの欠陥が顕著で、3次元に並べるとわずか15枚の平面に乗ってしまい、過去の科学計算に多くの誤った結論をもたらしました。

Mersenne Twister — 長周期と高次元均等分布

科学計算で長く事実上の標準だったのがMersenne Twister（MT19937）です。名前のとおり、周期がメルセンヌ素数 2^19937 − 1 という途方もない長さを持ちます。内部状態は32ビット語を624個（計19968ビット）並べた配列で、これをねじれ一般化フィボナッチ列として更新します。各ステップで状態語を線形変換（行列の積に相当するビット演算）で混ぜ、取り出した語に**テンパリング（tempering）**と呼ぶシフトとANDマスクの後処理を施して出力します。

MT19937の強みは長周期だけではありません。623次元均等分布という性質、すなわち連続する出力を623次元のベクトルとして並べても（32ビット精度で）一様に分布することが保証されます。LCGの格子問題を高次元まで回避しており、モンテカルロ法のように多数の独立した乱数を必要とする数値計算に向きます。

ただし弱点もあります。状態が大きく初期化（シード展開）が重いこと、出力が線形な変換だけで作られているため、連続する624語を観測すれば内部状態を完全に復元でき、将来も過去も予測できることです。また初期状態に0が多いと、しばらく質の悪い出力が続く「ゼロ過剰状態（zero-excess）」からの回復が遅いという既知の癖もあります。これらの理由から、後述のとおりMT19937は暗号用途には絶対に使えません。

PCGとxorshift — 小さな状態で良い品質を狙う

MTの「大きすぎる状態」と「予測しやすい線形性」への反省から、近年は小さな状態で統計品質を高める設計が主流になりました。代表がxorshift系とPCGです。

xorshiftは、状態に対してシフトとXORを数回繰り返すだけの軽量な生成器です。素のxorshiftは統計検定（後述のTestU01）に落ちる弱さがありますが、xorshift128+ や xoshiro256** のように、シフト・回転・加算や乗算を組み合わせた改良版は、64〜256ビットの状態で高速かつ良好な品質を達成し、多くの言語処理系の既定乱数になっています。

**PCG（Permuted Congruential Generator）**は発想が巧妙です。土台は予測しやすいLCGですが、その出力を直接返さず、状態に応じてビット回転量を変える置換（permutation）を後段にかけます。つまり「線形で進む状態遷移」と「非線形に見える出力置換」を分離し、LCGの弱い下位ビットと格子構造を出力置換で覆い隠します。状態64ビット程度でMTより良い統計性能を、はるかに小さなメモリと速度で実現できるのが売りです。

統計的品質はどう測るか

「乱数らしさ」は感覚ではなく統計検定で評価します。出力列を多数の検定（一様性、連の長さ、ビット間の相関、行列のランク、誕生日間隔など）にかけ、真の乱数なら起こりにくい偏りが出ないかを調べます。事実上の標準が TestU01 の検定バッテリ（SmallCrush / Crush / BigCrush）で、BigCrushを全て通ることが現代PRNGの最低ラインとされます。ほかに NIST SP 800-22、PractRand などが使われます。

検定をパスしても、それは「観測した範囲で乱数と区別できなかった」ことを意味するにすぎず、暗号的な安全性の証明ではありません。線形合同法やMTは多くの基本検定を通っても、内部状態の予測可能性という別次元の弱点を抱えたままです。統計品質と暗号強度はまったく別の評価軸である点が、次の節の核心です。

CSPRNGとの境界 — どこから「安全」が必要か

ここまでのPRNGは、出力を十分観測すれば残りの数列を予測できるという共通の急所を持ちます。LCGは数個、MT19937は624語を見れば内部状態を復元できます。シミュレーションでは問題になりませんが、セッショントークン、暗号鍵、パスワードリセット用トークン、ソルトの生成にこれを使うと、攻撃者が次の値を当てて成りすませる重大な脆弱性になります。

そこで境界を引くのが暗号論的に安全なPRNG（CSPRNG）です。CSPRNGは次の二つを満たします。(1) 次ビット予測不可能性 — これまでの出力を全部見ても、次のビットを1/2より有意に高い確率で当てられない。(2) 状態危殆化からの回復（前方秘匿性） — 仮に現在の内部状態が漏れても、過去に出した出力を逆算できない。これらは計算量的困難性（暗号プリミティブの安全性）に依拠して構成され、典型的にはブロック暗号のカウンタモードや、ChaCha20のようなストリーム暗号、ハッシュ関数を土台にします。

なお、CSPRNGも最初のエントロピー源（ハードウェアのノイズ、割り込みタイミング、RDRAND など）からシードされる必要があり、初期シードのエントロピーが不足すると安全性は崩れます。値の幅を絞るときの剰余バイアス（x % n は n が出力域を割り切らないと小さい値が出やすくなる）も、セキュア用途では拒否サンプリングで除く必要があります。これは整数演算の剰余と表現の落とし穴と地続きの問題です。

まとめ

PRNGは、シードから決定的に数列を生む有限状態機械であり、状態のビット幅が周期の上限を決めます。LCGは最速・最小だが下位ビットと格子構造が弱く、Mersenne Twisterは超長周期と高次元均等分布で科学計算の定番になった一方、線形ゆえに予測可能です。xorshift系・PCGは小さな状態で良い統計品質を狙う現代的な落としどころで、品質はTestU01などの検定で裏付けます。しかしこれらはすべて予測可能であり、鍵やトークンにはCSPRNGが要ります。統計的に乱数らしいことと、暗号的に予測できないことは別の保証であり、この境界を取り違えないことが安全なシステムの前提です。乱数の品質はハッシュ関数の撹拌とも設計思想を共有し、「散らす」技術として地続きに理解できます。