線形合同法

線形合同法︵せんけいごうどうほう、英: Linear congruential generators, LCGs︶とは、擬似乱数列の生成式の一つ。

漸化式

$X_{n+1}=\left(A\times X_{n}+B\right)\ {\bmod {\ }}M$$X_{n+1}=\left(A\times X_{n}+B\right)\ {\bmod {\ }}M$
によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B≥0である。

生成

上の式で、$X_{0}$ が、乱数の種であり、これに数を代入すると、$X_{1}$ が得られる。さらに$X_{2}$ を生成する場合には、$X_{1}$ を使う。以後、同様に行う。

例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種$X_{0}$ =8とすると、︵上の式においてはX_n+1を左辺に置いたが、今回は便宜上、右辺に置く︶

$\left(3\times 8+5\right)\ {\bmod {\ }}13=3$ 

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

$\left(3\times 3+5\right)\ {\bmod {\ }}13=1$ 

以下、同じように、

$\left(3\times 1+5\right)\ {\bmod {\ }}13=8$ 

となる。

周期性

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

(一)BとMが互いに素である。

(二)A-1が、Mの持つ全ての素因数で割りきれる。

(三)Mが4の倍数である場合は、A-1も4の倍数である。

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

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

長所

●状態を記憶するのに必要なメモリの他には、作業用のワーキングメモリをほとんど必要としない。実用的な擬似乱数アルゴリズムでは最少の部類に属する。

●低機能なプロセッサにも効率よく実装できる。素朴には乗算と除算が必要そうに見えるが、(1)定数による乗算なのでシフトと加減算の組合せにできる (2)除算そのものが必要なのではなく剰余が得られれば良いので合同算術による式変形が可能であり、乗算も含めて変形することでより効率化できる (3)剰余算についても、よく使われる2ⁿ-1 の形をした値による剰余は特別な場合として効率化ができる、といった特徴のためである。

●そのため、専用回路化すら容易である︵ただし、適切なM系列をLFSRで実装したほうが、回路で計算するにはより効率が良い上に、乱数としての質も良い︶。

●問題点は多いが、どのような問題があるか、どうやって回避すればいいかが十分に研究されている︵ただし、回避しなければならない使い方を回避していなかった事例を挙げて、悪い結果を生成系のせいにされていることがしばしば見られる︶。

短所

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

線形合同法一般の欠点に、多次元で規則的に分布するという性質がある。線形合同法による乱数列r₀, r₁, r₂, r₃, ... から(r₀, r₁), (r₁, r₂), (r₂, r₃), ... のように順番に割り当ててプロットすると、それが疎になるのはしょうがないのだが︵例として、全部で10000個しかない点を、10000x10000 の矩形にプロットすることになるのだから、稠密にはなりえない︶、一定の間隔の平面上に点が並んでしまうのが問題である。印象的にこれを表現したフレーズに Random numbers fall mainly in the planes. ︵乱数は、主に平面︵プレイン︶に落ちる︶というものがあり、﹁スペインの雨は主に平野︵プレイン︶に降る﹂︵The rain in Spain stays mainly in the plain.︶のパロディである。科学技術シミュレーションで3次元の点の位置などを生成する場合に問題となる。

下位ビットのランダム性が低い。Mの値によっては、最下位に近いビットはほとんどランダムでなく、完全に規則性を持っていることすらある。たとえばMが偶数の場合︵コンピュータでの実装が楽であるために、Mに2の冪を採用した場合はこれに当たる︶、最下位ビットは、同じものが出続けるか、0と1が交互にでるかのどちらかである。すなわち、偶数ばかりが出る、奇数ばかりが出る、偶数と奇数が交互に出る、のどれかになるということである︵最大周期ならば偶数と奇数が交互に出る︶。

大量に乱数列を消費する科学技術シミュレーションなどでは、周期の短さ︵たとえば32ビットでは最大周期でも約40億︶が問題になる。

プログラミング言語処理系に附属するライブラリの乱数列生成器︵たとえばrand(3)やjava.util.Randomなど︶が、線形合同法を利用している場合があるため、たとえばサイコロの目を生成する場合はrand() % 6 + 1としてはならない。前述のように周期2で偶数と奇数が循環するような場合、その規則性がそのまま顕れてしまう。rand() / (RAND_MAX / 6 + 1) + 1のようにすればランダムになる︵注。このコードは考え方を示すものであり、厳密に1/6の確率になるものではない︶。

例

Park & Miller

Stephen K. Park と Keith W. Miller が、彼らのサーベイ中で﹁最低基準﹂として示したもので、より良い選択肢が無いのならば、自作などせずにこれを使うべしというもの。

$X_{n+1}=\left(48,271\times X_{n}\right)\ {\bmod {\ }}(2^{31}-1)$ 

C言語による実装例が﹁comp.lang.c FAQ list · Question 13.15﹂の回答中にある。

由来不詳

由来不詳だが、よく実装が見られるもの。

$X_{n+1}=\left(1,103,515,245\times X_{n}+12,345\right)\ {\bmod {\ }}2^{32}$ 

C言語による実装例が、POSIXのrandの解説中︵informative扱いのEXAMPLESとして、であるが︶にあるためか、2017年現在のウェブコンテンツなどにも時折見られるが︵例えばRosetta Codeの線形合同法のサンプルに﹁BSD formula﹂という名前で示されている︶前節のPark & Millerよりも質が悪い。特に︵POSIXにあるコードでは下位桁を捨てて回避しているが︶、最下位ビットは周期2、次のビットは周期4、次のビットは周期8、……のように、下位桁に完全な規則性がある。また、由来は不詳だが少なくともBSDよりは古く、Unixバージョン7の /usr/src/libc/gen/rand.c に見られる。

参考文献

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

関連項目

• Permuted congruential generator - 線形合同法の出力を加工して統計的性質を改善したアルゴリズム。