線形合同法

線形合同法（せんけいごうどうほう、）とは、擬似乱数列の生成式の一つ。
漸化式
によって与えられる。A、B、Mは定数で、M>A、M>B、A>0、B≥0である。
生成.
上の式で、formula_2が、乱数の種であり、これに数を代入すると、formula_3が得られる。さらにformula_4を生成する場合には、formula_3を使う。以後、同様に行う。
例えば、定数をそれぞれ、A=3、B=5、M=13、乱数の種formula_2=8とすると、（上の式においてはXn+1を左辺に置いたが、今回は便宜上、右辺に置く）
次に乱数を生成する際は前回生成された乱数（今回は3）を使って、
以下、同じように、
となる。
周期性.
生成される乱数列は周期性を持ち、上の例では8→3→1→8→3→……、を繰り返す。この周期は最大でMであり、以下の条件が満たされたときに最大周期Mをもつ。
A=13、B=5、M=24の組み合わせなどがそれに当たる。
B=0のときは、0→0→0...というループがあるため、周期がMとなるAとMの組合せはない。M-1が、B=0の場合の最大の周期であり、これも最大周期と考えることもある。
短所.
暗号論的擬似乱数生成器ではなく、そのまま暗号に使用してはならない。
線形合同法一般の欠点に、多次元で規則的に分布するという性質がある。線形合同法による乱数列r0, r1, r2, r3, ... から(r0, r1), (r1, r2), (r2, r3), ... のように順番に割り当ててプロットすると、それが疎になるのはしょうがないのだが（例として、全部で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)やcodice_1など）が、線形合同法を利用している場合があるため、たとえばサイコロの目を生成する場合はcodice_2としてはならない。前述のように周期2で偶数と奇数が循環するような場合、その規則性がそのまま顕れてしまう。codice_3のようにすればランダムになる（注。このコードは考え方を示すものであり、厳密に1/6の確率になるものではない）。
例.
Park & Miller.
Stephen K. Park と Keith W. Miller が、彼らのサーベイ中で「最低基準」として示したもので、より良い選択肢が無いのならば、自作などせずにこれを使うべしというもの。
C言語による実装例が「comp.lang.c FAQ list · Question 13.15」の回答中にある。
由来不詳.
由来不詳だが、よく実装が見られるもの。
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 に見られる。