线性同余方法

线性同余方法（LCG）是个产生伪随机数的方法。

它是根据以下的递回关系式：

${\displaystyle N_{j+1}\equiv (A\times N_{j}+B){\pmod {M}}}$

其中${\displaystyle A,B,M}$是产生器设定的常数。

LCG的周期最大为${\displaystyle M}$，但大部分情况都会少于M。要令LCG达到最大周期，应符合以下条件：

1. ${\displaystyle B,M}$互质；
2. ${\displaystyle M}$的所有质因数都能整除${\displaystyle A-1}$；
3. 若${\displaystyle M}$是4的倍数，${\displaystyle A-1}$也是；
4. ${\displaystyle A,B,N_{0}}$都比${\displaystyle M}$小；
5. ${\displaystyle A,B}$是正整数。