線形合同法

線形合同法（せんけいごうどうほう、Linear congruential generators,LCGs）とは、擬似乱数列を生成するアルゴリズムの一つ。

漸化式

<math>X_{n+1} = \left( A \times X_n + B \right) \bmod M</math>

によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B≥0である。

生成

上の式で、<math>X_0</math>が、乱数の種であり、これに数を代入すると、<math>X_1</math>が得られる。さらに<math>X_2</math>を生成する場合には、<math>X_1</math>を使う。以後、同様に行う。

例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種<math>X_0</math>=8とすると、（上の式においてはX_n+1を左辺に置いたが、今回は便宜上、右辺に置く）

<math>\left( 3 \times 8 + 5 \right) \bmod 13 = 3</math>

次に乱数を生成する際は前回生成された乱数（今回は3）を使って、

<math>\left( 3 \times 3 + 5 \right) \bmod 13 = 1</math>

以下、同じように、

<math>\left( 3 \times 1 + 5 \right) \bmod 13 = 8</math>

となる。

周期性

生成される乱数列は周期性を持ち、上の例では8→3→1→8→3→……、を繰り返す。この周期は最大でMであり、以下の条件が満たされたときに最大周期Mをもつ。

1. BとMが互いに素である。
2. A-1が、Mの持つ全ての素因数で割りきれる。
3. Mが4の倍数である場合は、A-1も4の倍数である。

A=13、B=5、M=24の組み合わせなどがそれに当たる。

B=0のときは、0→0→0...というループがあるため、周期がMとなるAとMの組合せはない。M-1が、B=0の場合の最大の周期であり、これも最大周期と考えることもある。

長所

• ほとんど記憶領域を必要としない。実用的な擬似乱数アルゴリズムでは最少である。
• 低機能なプロセッサ上でも極めて高速である。素朴な実装では乗算と除算が必要だが、有限代数を使って回避できる。
• 単純な演算しか使わないため専用回路化が容易である。
• 問題点は多いが、どのような問題があるか、どうやって回避すればいいかが十分に研究されている。

短所

暗号論的擬似乱数生成器ではなく、そのまま暗号に使用してはならない。

線形合同法一般の欠点に、多次元で均等分布しない性質がある。線形合同法による乱数列r₁, r₂, r₃, r₄, ... から(x₁, y₁), (x₂, y₂), ... のように順番に割り当ててプロットすると、一定の間隔の格子点上に点が並んでしまう。科学技術シミュレーションで3次元の点の位置などを生成する場合に問題となる。

下位ビットのランダム性が低い。特にMが偶数の場合（コンピュータでの実装が楽であるために、Mに2の冪を採用した場合はこれに当たる）、最下位ビットは、同じものが出続けるか、0と1が交互にでるかのどちらかである。すなわち、偶数ばかりが出る、奇数ばかりが出る、偶数と奇数が交互に出る、のどれかになるということである（最大周期ならば偶数と奇数が交互に出る）。

大量の擬似乱数を使う科学技術シミュレーションなどでは、周期の短さ（たとえば32ビットでは最大周期でも約40億）が問題になる。

プログラミング言語処理系に附属するライブラリの乱数生成器（たとえばrand(3)）が、線形合同法を利用している場合があるため、たとえばサイコロの目を生成する場合はrand() % 6 + 1とするのではなくrand() / (RAND_MAX / 6 + 1) + 1のようにすれば各数値の発生確率が均等に近づく（注。このコードは考え方を示すものであり、厳密に1/6の確率になるものではない）。これは、処理系依存であるRAND_MAXが一般的に6で割り切れない数値のため、%演算では1から6の数字が均等に発生しない事が原因である。RAND_MAXが大きいほど、rand() % 6 + 1のコードは均等な発生確率に収束する。 しかしながら強力なランダム性が必要であれば、そもそも線形合同法ではなく別のアルゴリズムを利用するべきである。

参考文献

1. Park and Miller, "Random Number Generators: Good Ones are Hard to Find"
2. 結城浩著『暗号技術入門 - 秘密の国のアリス』、ソフトバンク、ISBN 4-7973-2297-7、pp.305-307.