プログラミングやシミュレーション、暗号技術を学んでいると登場する「線形合同法」。
「乱数生成にアルゴリズムがあるの？」「擬似乱数って何が擬似なの？」と疑問に感じる方も多いでしょう。
本記事では、線形合同法の意味・仕組み・パラメータの役割から、周期の性質・擬似乱数との関係・実際の使い方まで、わかりやすく解説していきます。
数学的な背景も丁寧に説明しますので、ぜひ最後までご覧ください。
線形合同法とは？意味と基本的な仕組み
それではまず、線形合同法の基本的な意味と仕組みについて解説していきます。
線形合同法（Linear Congruential Generator, LCG）とは、簡単な漸化式を使って擬似乱数を生成するアルゴリズムです。
1948年にD.H.ルーマーによって提案された比較的古い手法ですが、シンプルで高速なため今でも広く使われています。
基本的な漸化式は次のとおりです。
【線形合同法の漸化式】
Xₙ₊₁ = (a × Xₙ + c) mod m
X₀：初期値（シード値）
a：乗数（multiplier）
c：増分（increment）
m：法（modulus）
この式は「前の値 Xₙ を a 倍して c を足し、m で割った余り」を次の値として使う、という非常にシンプルな計算です。
シード値（X₀）を変えることで、異なる乱数列を生成できます。
コンピュータの乱数生成では、多くの場合この線形合同法かその改良版が使われています。
各パラメータの役割と選び方
線形合同法の性質は、パラメータ（a, c, m）の選び方によって大きく変わります。
| パラメータ | 名称 | 役割と注意点 |
|---|---|---|
| m | 法（モジュラス） | 生成される数の範囲（0〜m-1）を決める。大きな値（例：2³²）が一般的 |
| a | 乗数 | 乱数列の統計的性質に大きく影響。適切な値を選ぶことが重要 |
| c | 増分 | 0の場合を特に「乗算合同法」と呼ぶ。c≠0の場合は「混合合同法」 |
| X₀ | シード値 | 乱数列の出発点。同じシードからは同じ列が生成される |
パラメータの代表的な例として、CランタイムライブラリではしばしばN a=1103515245, c=12345, m=2³²が使われてきました。
適切なパラメータを選ばないと、乱数の品質が著しく低下する可能性があります。
擬似乱数とは何か
線形合同法が生成するのは「擬似乱数（Pseudo-Random Number）」です。
真の乱数は予測不可能な物理的現象（熱雑音・放射性崩壊など）から得られますが、コンピュータは決定論的な機械であるため、純粋な意味での乱数を生成することはできません。
そこで、決定論的なアルゴリズムで計算した数列が「乱数のように見える（ランダム性の統計的テストに合格する）」ものを擬似乱数と呼びます。
擬似乱数の特徴は、同じシード値からは必ず同じ数列が再現できるという点です。
これは科学的シミュレーションや機械学習の実験の再現性を確保する上で非常に有用な性質です。
シード値の重要性
線形合同法を含む擬似乱数生成器では、シード値（初期値）の設定が非常に重要です。
シード値が同じであれば生成される乱数列は完全に同じになるため、実験の再現が可能です。
一方、セキュリティ上の目的では予測不可能なシード値（現在時刻・OS提供のエントロピーなど）を使う必要があります。
Pythonでは random.seed(42) のようにシード値を設定することで、再現可能な乱数列を得ることができます。
周期と線形合同法の品質
続いては、線形合同法の「周期」という重要な性質について確認していきます。
擬似乱数生成器は有限のパラメータで動作するため、いつかは同じ値が繰り返し登場します。
この繰り返しが始まるまでの乱数の個数を「周期（period）」と呼びます。
最大周期の条件（ハル＝ドーベル定理）
線形合同法の周期を最大（= m）にするための条件は「ハル＝ドーベル定理」として知られています。
【最大周期の条件】
①c と m は互いに素（gcd(c, m) = 1）
②m の素因数 p すべてに対して、(a-1) が p の倍数
③m が 4 の倍数ならば、(a-1) も 4 の倍数
これらの条件を満たすパラメータを選ぶことで、周期を最大 m にすることができます。
周期が短いと同じパターンが繰り返され、乱数としての品質が低下してしまいます。
線形合同法の統計的品質と問題点
線形合同法はシンプルで高速という長所を持ちますが、いくつかの問題点もあります。
最大の問題は、高次元空間でのランダム性が低いことです。
連続するいくつかの乱数を組み合わせて高次元のベクトルを作ると、それらが少数の超平面上に並んでしまう「格子構造」という現象が起きます。
モンテカルロシミュレーションなど高次元の乱数を必要とする用途には適していません。
また、暗号学的な用途（パスワード生成・セキュリティトークンなど）には線形合同法は使うべきではなく、暗号論的擬似乱数生成器（CSPRNG）を使う必要があります。
メルセンヌツイスターとの比較
現代のプログラミング言語では、線形合同法の代わりに「メルセンヌツイスター（MT）」が広く使われています。
Pythonの random モジュールやC++の標準ライブラリでも、デフォルトはメルセンヌツイスターです。
| 比較項目 | 線形合同法 | メルセンヌツイスター |
|---|---|---|
| 周期 | 最大 m（通常2³²程度） | 2¹⁹⁹³⁷ – 1（非常に長い） |
| 高次元均一性 | 低い（格子構造の問題） | 623次元まで均一 |
| 速度 | 非常に高速 | 高速 |
| 実装の簡単さ | 非常に簡単 | やや複雑 |
| 暗号安全性 | 低い | 低い（用途外） |
一般的な用途ではメルセンヌツイスターが推奨されますが、組み込みシステムや教育目的では線形合同法の簡潔さが活きる場面もあります。
線形合同法の実装と活用
続いては、線形合同法の実際の実装例と活用場面を確認していきます。
Pythonによる実装例
線形合同法はPythonで非常に簡単に実装できます。
【PythonによるLCGの実装例】
def lcg(seed, a=1664525, c=1013904223, m=2**32):
x = seed
while True:
x = (a * x + c) % m
yield x / m # 0〜1の範囲に正規化
gen = lcg(42)
for _ in range(5):
print(next(gen))
このコードでは、seed=42 を出発点として乱数列を無限に生成するジェネレーターを実装しています。
yield x / m により0以上1未満の浮動小数点乱数を生成しています。
ゲームやシミュレーションでの活用
線形合同法は特にゲームプログラミングやシミュレーションで活用されてきた歴史があります。
ゲームのプロシージャルコンテンツ生成（PCG）では、シード値を変えることで毎回異なるマップ・ダンジョン・敵配置を生成できます。
科学的シミュレーションでは、モンテカルロ法の乱数源として線形合同法が使われることもあります。
ただし、高精度なシミュレーションには品質の高い乱数生成器を選ぶことが重要です。
乱数の品質テストとDiehard Tests
乱数生成器の品質を評価するためのテストセットとして「Diehard Tests」や「TestU01」などが知られています。
これらのテストは、生成された乱数列の統計的ランダム性を様々な観点から検証します。
線形合同法はシンプルなテストには合格しますが、高度なテストでは問題点が露呈することがあります。
用途に応じて適切な乱数生成器を選択することが重要でしょう。
まとめ
本記事では、線形合同法の意味・仕組み・パラメータの役割・周期・擬似乱数との関係・実装例・活用場面について詳しく解説しました。
線形合同法は「Xₙ₊₁ = (a × Xₙ + c) mod m」という単純な漸化式で擬似乱数を生成する手法です。
シンプルで高速という長所がある一方、高次元での乱数品質の低さや暗号安全性の欠如という限界もあります。
現代の多くの用途ではメルセンヌツイスターなどより高品質な生成器が使われますが、線形合同法の仕組みを理解することは擬似乱数の基礎を学ぶ上で非常に有益です。
ぜひ実際にコードを書いて、線形合同法の動作を体験してみてください。
