線形合同法（LCG）の基礎と周期条件から実装上の注意点・評価・代替手法まで徹底解説

2025年11月23日 最終更新日時 : 2025年11月23日 エバープレイ編集部

はじめに — 線形合同法とは何か

線形合同法（せんけいこうどうほう、Linear Congruential Generator: LCG）は、擬似乱数生成アルゴリズムの代表的な一つで、次の漸化式で定義されます。

X = (a × X + c) mod m

ここで m（法）、a（乗数）、c（加算子、増分）、X<0>（種、シード）は整数パラメータです。実装が非常に単純で高速なため、歴史的にも広く用いられてきました。しかし単純さゆえの弱点も多く、用途に応じた理解と注意が必要です。

数学的な基本性質

  • パラメータ
    • m（モジュラス）: 生成される値は 0 から m−1 まで。
    • a（乗数）: 状態を掛ける係数。
    • c（増分）: 加える定数。c = 0 の場合は「乗法的LCG（multiplicative LCG）」と呼ばれる。
    • X0（シード）: 初期状態。異なるシードは別系列を生む。
  • 周期（周期長）
    • 有限状態（m通り）のため周期は必ず存在します。良いパラメータを選べば最大周期（mixed LCG なら m）を得ることができます。
    • 完全周期を得るための必要十分条件は Hull–Dobell の定理で与えられます（次節参照）。
  • 分布と相関
    • 1次元では一見一様に見えても、高次元では格子（lattice）構造を示し、多次元散布図に平面や格子状のパターンが現れる（Marsagliaの指摘）。
    • 特に m が 2^k のような冪乗のとき低位ビットは周期が短く相関が強くなりやすい。

周期に関する条件 — Hull–Dobell の定理

線形合同法 X = (a X + c) (mod m) が周期 m（すなわち全ての 0..m−1 を巡る）を持つための条件は次の三つです（Hull & Dobell, 1962）：

  • c と m は互いに素（gcd(c, m) = 1）であること。
  • a − 1 は m のすべての素因子を割り切ること（すべての p | m に対し p | (a−1)）。
  • もし m が 4 で割り切れるなら a − 1 は 4 で割り切れること。

乗法的（c = 0）場合は条件が変わり、例えば m が素数のとき a が原始根（primitive root）であれば最大周期 m−1 を得ます。

代表的な実装例と歴史的失敗例

  • RANDU（1970年代によく使われた）: m = 2^31, a = 65539, c = 0。これは著名な失敗例で、3次元散布図に平面が現れるなど品質が非常に悪い。
  • Park–Miller（「minimal standard」）: m = 2^31 − 1（2147483647, 素数）、a = 16807, c = 0。比較的良好で軽量な乗法的LCGの例。
  • Java の java.util.Random: 48ビット状態の LCG（a = 25214903917, c = 11, m = 2^48）。高速で実用的だが暗号用途には不適。
  • Microsoft Visual C の rand(): 32ビット計算で state = state * 214013 + 2531011; 戻り値は上位ビットを取る方式。用途によっては十分でないことがある。

統計的検定と品質評価

LCG の品質は単なる一様性だけで評価できません。多次元相関、周期長、位相別の均等性などを調べるために Diehard、TestU01 などのバッテリが用いられます。良いLCGでも特定の検定に弱い場合があるため、用途（モンテカルロ、シミュレーション、ゲーム）に応じた評価が必要です。

実装上の注意点

  • 整数のオーバーフロー: 計算の掛け算 a × X はオーバーフローしやすい。言語の型（符号付/符号無）とビット幅を明確に意識し、必要ならばより大きい型を用いて正しいモジュロを取る。
  • モジュロが 2^k のときはビットマスクによる高速化が可能だが、低位ビットの品質が劣るため用途に注意。
  • 低位ビットの切り捨て: power-of-two モジュロを使う実装では下位ビットをそのまま乱数として使うと非常にまずい。上位ビットを採るか、ビット混合を行うべき。
  • シード初期化: time() のみを使った簡易シードは衝突を招きやすい。並列やクラウド環境では特に注意し、OSのエントロピー（/dev/urandom、getrandom()、CryptGenRandom など）を利用すること。

用途別の適否 — どこで使えるか、使えないか

  • モンテカルロ計算やシミュレーション: 高品質な LCG（適切に選ばれたパラメータ）で十分な場合があるが、高次元依存性に注意。厳密な統計的精度が必要な場面ではより強力な PRNG（例: Mersenne Twister, PCG, xoshiro）や検定が推奨される。
  • ゲームやグラフィックス: パフォーマンス重視なら LCG は有用。ただし同一シードによる再現性や、低位ビットの安定性に注意。
  • 暗号（鍵生成、トークン等）: 絶対に使用不可。LCG は簡単に予測可能で、内部状態が少ないため復元が容易。暗号用途では CSPRNG（/dev/urandom、getrandom、libsodium、OpenSSL の RAND_bytes など）を使う。

改善方法と代替アルゴリズム

  • 改良手法
    • 複数の LCG を組み合わせる（和やXORを取る）ことで格子構造を緩和する手法があるが、正しく設計しないと新たな相関を生む。
    • ビット混合（scrambling）して出力ビットを均す。
  • 現代的代替
    • Mersenne Twister（MT19937）: 非常に長い周期と良好な統計特性。科学計算で広く使われるが、初期配列の弱点や並列実行時の扱いに注意。
    • PCG（Permuted Congruential Generator）: LCGの高速性を活かしつつビットパーミュテーションで品質を向上させた最近の手法。
    • Xorshift / xoshiro 系: 高速で良好な品質だが設計によっては特定ビットの弱さがある。
    • 暗号用には ChaCha20 や AES-CTR ベースの CSPRNG を使用。

並列化と複数ストリームの扱い

大規模並列処理で同じ LCG を各スレッドで使うと周期のオフセットや相関の問題が生じる。対策としては：

  • ストリーム分割（jump-ahead／skip-ahead）で互いに重ならないシード領域を与える。
  • パラメータを変えた独立した PRNG を用意する（ただしパラメータ選びは注意深く）。
  • 各スレッドごとに独立な高品質 PRNG インスタンス（mt19937_64 や xoshiro）を割り当てる。

実務的な推奨事項

  • 汎用用途（簡易な乱数が欲しい、再現性が重要）→ 良く設計された LCG（例: Park–Miller）や std::minstd_rand 等の検証済み実装を検討。
  • 統計的精度が重要→ Mersenne Twister、PCG、xoshiro などを使用し、TestU01 等で検証する。
  • 暗号用途→ OS が提供する CSPRNG（getrandom(), /dev/urandom, CryptGenRandom など）や libsodium/OpenSSL の API を利用。
  • 実装では符号なし整数型を使い、乗算で高精度が必要な場合は幅の広い型（64ビットや128ビット）で中間結果を扱う。

まとめ

線形合同法は歴史的に重要で、理解しておくべき基本的な擬似乱数生成手法です。実装が簡単で高速という利点がある一方、正しいパラメータ選択や使い方を怠ると致命的な相関や短い周期に悩まされます。用途に応じて適切な PRNG を選び、暗号用途には決して使わないことを強く推奨します。

参考文献

カテゴリー
IT
前の記事
Hans Sotin（ハンス・ゾーティン）— バス歌手の経歴・歌唱特徴・名盤ガイドNew!!
2025年11月23日
次の記事
メルセンヌ・ツイスタ（MT19937）徹底解説：歴史・仕組み・長所・短所と現代の代替RNGガイドNew!!
2025年11月23日