線形合同法（せんけいごうどうほう、）とは、擬似乱数列の生成式の一つ。漸化式によって与えられる。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とすると、（上の式においてはXを左辺に置いたが、今回は便宜上、右辺に置く）次に乱数を生成する際は前回生成された乱数（今回は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の場合の最大の周期であり、これも最大周期と考えることもある。暗号論的擬似乱数生成器ではなく、そのまま暗号に使用してはならない。線形合同法一般の欠点に、多次元で疎に分布するという性質がある。線形合同法による乱数列r, r, r, r, ... から(r, r), (r, r), ... のように順番に割り当ててプロットすると、一定の間隔の格子点状に点が並んでしまう。科学技術シミュレーションで3次元の点の位置などを生成する場合に問題となる。下位ビットのランダム性が低い。Mの値によっては、最下位に近いビットは完全にランダムでなく規則性を持っていることすらある。たとえばMが偶数の場合（コンピュータでの実装が楽であるために、Mに2の冪を採用した場合はこれに当たる）、最下位ビットは、同じものが出続けるか、0と1が交互にでるかのどちらかである。すなわち、偶数ばかりが出る、奇数ばかりが出る、偶数と奇数が交互に出る、のどれかになるということである（最大周期ならば偶数と奇数が交互に出る）。大量に乱数列を消費する科学技術シミュレーションなどでは、周期の短さ（たとえば32ビットでは最大周期でも約40億）が問題になる。プログラミング言語処理系に附属するライブラリの乱数列生成器（たとえばrand(3)やcodice_1など）が、線形合同法を利用している場合があるため、たとえばサイコロの目を生成する場合はcodice_2としてはならない。前述のように周期2で偶数と奇数が循環するような場合、その規則性がそのまま顕れてしまう。codice_3のようにすればランダムになる（注。このコードは考え方を示すものであり、厳密に1/6の確率になるものではない）。

出典:wikipedia