概述
线性同余发生器（Linear congruential generator），简称LCG，是一种能产生具有不连续计算的伪随机序列的分段线性方程的算法，它代表了最古老和最知名的伪随机序列生成器算法之一，其理论相对容易理解，并且易于实现和快速，特别是在可以通过存储位截断提供模运算的计算机硬件上。
作为流密码（stream cipher）中常用的伪随机数发生器（pseudo random number generator），其随机性能取决于参数和种子的选择。
递推公式
$S_{n+1} \equiv aS_{n}+b (\mod m)$
参数
- $S$代表伪随机序列
- $m$，$0<m$ 表示模量
- $a$， $0<a<m$ 表示乘数
- $b$， 表示增量
- $S_0$，$0 \leq S_0<m$ 表示初始值
阶
$a$与$n$互素，使得
$a^x \equiv 1 \mod n$
成立的最小正整数$x$称为$a$模$n$的阶，记为$ordn(a)$。
原根
如果有
$ordn(a)=\phi (n)$
称a为模n的原根
若$gcd(a,m)=1$，则周期$T=ordm(a)$，所以选取系数时应尽量使得a为模m的原根，以此尽量延长LCG周期。
常见推导公式
公式一
此公式用于从$S_{n+1}$反推出$S_n$，公式如下
$S_n=(a^{-1}(S_{n+1}-b))\%m$
推导过程如下
$S_{n+1}-b \equiv aS_{n} (\mod m)$
进而
$S_n=(a^{-1}(S_{n+1}-b))\%m$。
公式二
此公式用于求$a$，公式如下
$a=((S_{n+2}-S_{n+1})(S_{n+1}-S_n)^{-1})\%m$
推导过程如下
$S_{n+2} \equiv aS_{n+1}+b \mod m$
$ S_{n+1} \equiv aS_{n}+b \mod m $
两式相减
$(S_{n+2}-S_{n+1}) \equiv a(S_{n+1}-S_n) \mod m$
进而得到
$a=((S_{n+2}-S_{n+1})(S_{n+1}-S_n)^{-1})\%m$
公式三
此公式用于求$b$，公式如下
$b=(S_{n+1}-aS_{n})\%m$
公式四
此公式用于求$m$，公式如下
令$t=S_{n+1}-S_n$，则$m=gcd((t_{n+1}t_{n-1}-t_n^2),(t_nt_{n-2}-t_{n-1}^2))$
推导过程如下
令 $t=S_{n+1}-S_n$ ，有
$t_n \equiv (aS_n+b)-(as_{n-1}+b) \equiv at_{n-1} \mod m$
$t_{n+1}t_{n-1}-t_n^2 \equiv (aat_{n-1}t_{n-1}-at_{n-1}at_{n-1}) \equiv 0 \mod m$
即$T_n= t_{n+1}t_{n-1}-t_n^2$ 为$m$的倍数，求$T_n$、$T_{n-1}$最大公因数即为$m$，所以
$m=gcd((t_{n+1}t_{n-1}-t_n^2),(t_nt_{n-2}-t_{n-1}^2))$