LCG（線形合同法）の基礎・限界・実装のポイントと現代の代替乱数ガイド
エバープレイ編集部はじめに — LCG（線形合同法）とは何か
LCG（Linear Congruential Generator、線形合同法）は、最も古典的で広く知られた疑似乱数生成アルゴリズムの一つです。単純な再帰式により疑似乱数列を生成するため、実装が容易で計算コストも小さい反面、統計的性質や安全性の面で限界があります。本稿では、数学的な性質、実装上の注意点、代表的な失敗例、評価方法、実務での代替案までを深掘りします。
基本式とパラメータ
LCGは次の漸化式で定義されます。
- X_{n+1} = (a * X_n + c) mod m
ここで、
- m：モジュラス（周期の上限となる正整数）
- a：乗数（multiplier）
- c：増分（increment）。c=0 の場合は「乗法型（multiplicative）LCG」またはLehmer型と呼ばれる。
- X_0：シード（初期値）
生成される整数列 X_n の最大周期は m（c≠0 の場合、適切な条件が満たされれば周期 m を得られる）または m−1（c=0 で m が素数かつ a が原根の場合）です。
完全周期を得る条件（Hull–Dobellの定理）
c ≠ 0 の一般的な LCG で周期を m にするための必要十分条件は Hull–Dobell の定理で与えられます。要点は次の通りです。
- c と m は互いに素であること。
- a − 1 は m のすべての素因子を割り切ること。
- もし m が 4 の倍数なら、a − 1 は 4 の倍数であること。
これらを満たせば、どのシード X_0 を選んでも周期 m の列が得られます。ただし「周期が長い＝統計的に優れている」ではない点に注意が必要です。
代表的な実装例と失敗例
- RANDU（歴史的に有名な失敗例）：a=65539, c=0, m=2^31。多次元で明確な平面上に点が並ぶなど強い相関が観察され、1960年代から問題視されてきました。
- ANSI C の簡易実装（多くの実装で採用された係数）：a=1103515245, c=12345, m=2^31（あるいは 2^32）。手軽だが低次ビットの質が悪いことが知られます。
- Park–Miller（Minimal Standard）：乗法型で a=16807, m=2^31−1（2147483647）。Lehmer 系の改良で、当時の標準的な選択肢として普及しました。
- Visual C の古い実装など：特定の係数（例：a=214013, c=2531011 等）を使い、上位ビットを返す実装が採られていましたが、低次ビットの質は依然として低いです。
（上記の係数や失敗例は公知の事例であり、後掲の参考文献で確認できます。）
統計的な問題点 — 格子構造と低次ビットの偏り
LCG の本質的な弱点はいくつかあります。
- 格子（lattice）構造：高次元において、LCG が生成する点は有限個の平面や格子上に並びやすいことが知られています（“random numbers fall mainly in the planes”）。これにより、モンテカルロ法など多次元サンプリングに使うと誤差やバイアスを招く可能性があります。
- 低次ビットの質が悪い：m が 2^k の場合、下位ビットは極端に短い周期を持つことがあるため、ビット単位で乱数を使う用途（ビットマスク、ビット操作）では注意が必要です。よくある対策は高次ビットを使う、あるいはビットを混合して返すことです。
- 初期のシード依存：特定のシードから始めると短期間で周期や相関の影響が出る場合があります。warm-up（捨て出し）をする実装もありますが万能ではありません。
- 暗号用途には不適当：線形性が強く、観測された出力から内部状態を復元できるため、暗号学的な安全性はありません。
評価方法 — スペクトルテストや統計検定
LCG の評価には様々なテストが使われます。
- スペクトルテスト（spectral test）：LCG の格子構造を定量化する手法で、最悪の場合の点の平面間隔を調べます。良い係数選びの指標になります。
- Diehard 系やTestU01：実用的な統計検定スイートで、乱数列に対して多数の独立検定を行い偏りや相関を検出します。実装の健全性確認に広く使われます。
- 周期の長さ確認：理論上の周期と実際に得られる周期を比較し、周期性が問題にならないか確認します。
実装上の注意と改善策
実務で LCG を使う際の実装上の注意点と、弱点を緩和するための手法を挙げます。
- 中間演算では十分に大きな型を使う：乗算時のオーバーフローを避けるため、64 ビット整数で計算するなどの対策を取る。
- 下位ビットを直接利用しない：出力に上位ビットを使う、あるいはビット混合（例えば乱数を右シフトして高次ビットを返す）を行う。
- 複数の生成器を合成する：LCG の出力を別の系列で XOR するなどして性質を改善する手法。ただし安全性・統計性の保証は別途検証が必要。
- 良く選ばれた係数を使う：スペクトルテストや既存の研究で良好とされる係数（例：Park–Miller の a=16807 といったもの）を使う。
- 暗号的用途や高度な統計用途ではモダンな代替手段を選ぶ（次節参照）。
現代の代替乱数生成器（推奨）
LCG は簡便さゆえに今でも一部で利用されますが、現代では次のようなより高品質な擬似乱数生成器が推奨されます。
- Mersenne Twister（MT19937）：非常に長い周期（2^19937−1）と良好な統計特性を持ち、科学計算で広く採用。
- xorshift / xoroshiro / xoshiro 系：ビット操作を主体とした高速で良好な統計特性を持つ生成器。
- PCG（Permuted Congruential Generator）：LCG の利点（シンプルさ）を残しつつ出力を写像して統計性を改善した設計。実装とパラメータ選択の研究が進んでいます。
- 暗号学的 PRNG（例：ChaCha20 ベース等）：暗号用途では推測耐性のある生成器を用いること。
現場での判断基準
どの乱数生成器を採用するかは用途に依存します。簡易なサンプリングや非クリティカルな用途では適切な係数の LCG でも実用的ですが、次の場合はより強力な生成器を選ぶべきです。
- 金融や物理シミュレーションなど高精度が要求されるモンテカルロ法
- 暗号学的用途（鍵生成、トークン発行など）
- 並列分散環境での再現性・独立性が要求される場合
まとめ
LCG はアルゴリズムとして非常にシンプルで理解しやすく、古くから多くのシステムで使われてきました。一方で格子構造や低次ビットの偏り、暗号的安全性の欠如など明確な欠点も持ちます。現在は用途に応じて Mersenne Twister、xorshift 系、PCG、もしくは暗号学的 PRNG を選ぶのが一般的です。どうしても LCG を使う場合は、Hull–Dobell の条件に従った係数選定、十分な内部幅での実装、出力ビットの取り扱いに注意してください。
参考文献
- Linear congruential generator — Wikipedia
- Hull–Dobell theorem — Wikipedia
- RANDU — Wikipedia (historical example)
- George Marsaglia, "Random numbers fall mainly in the planes", Proceedings of the National Academy of Sciences (1968)
- Park & Miller "Minimal Standard" discussion and implementations
- 乱数生成器に関する技術的解説（教育的資料）
- PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation
- Mersenne Twister — 原論文と実装（Matsumoto & Nishimura）
投稿者プロフィール
