概述

线性同余发生器（Linear congruential generator），简称LCG，是一种能产生具有不连续计算的伪随机序列的分段线性方程的算法，它代表了最古老和最知名的伪随机序列生成器算法之一，其理论相对容易理解，并且易于实现和快速，特别是在可以通过存储位截断提供模运算的计算机硬件上。

作为流密码（stream cipher）中常用的伪随机数发生器（pseudo random number generator），其随机性能取决于参数和种子的选择。

递推公式

$S_{n+1}\equiv a{S}_n+b(\mathrm{mod}m)$

参数

• $S$代表伪随机序列
• $m$，$0<m$ 表示模量
• $a$， $0<a<m$ 表示乘数
• $b$， 表示增量
• $S_0$，$0\le S_0<m$ 表示初始值

阶

$a$与$n$互素，使得

$a^x\equiv 1\mathrm{mod}n$

成立的最小正整数$x$称为$a$模$n$的阶，记为$ordn(a)$。

原根

如果有

$ordn(a)=\varphi (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))\mathrm{\%}m$

推导过程如下

$S_{n+1}-b\equiv a{S}_n(\mathrm{mod}m)$

进而

$S_n=(a^{-1}(S_{n+1}-b))\mathrm{\%}m$。

公式二

此公式用于求$a$，公式如下

$a=((S_{n+2}-S_{n+1})(S_{n+1}-S_n{)}^{-1})\mathrm{\%}m$

推导过程如下

$S_{n+2}\equiv a{S}_{n+1}+b\mathrm{mod}m$

$S_{n+1}\equiv a{S}_n+b\mathrm{mod}m$

两式相减

$(S_{n+2}-S_{n+1})\equiv a(S_{n+1}-S_n)\mathrm{mod}m$

进而得到

$a=((S_{n+2}-S_{n+1})(S_{n+1}-S_n{)}^{-1})\mathrm{\%}m$

公式三

此公式用于求$b$，公式如下

$b=(S_{n+1}-a{S}_n)\mathrm{\%}m$

公式四

此公式用于求$m$，公式如下

令$t=S_{n+1}-S_n$，则$m=gcd((t_{n+1}{t}_{n-1}-t_n^2),(t_n{t}_{n-2}-t_{n-1}^2))$

推导过程如下

令 $t=S_{n+1}-S_n$ ，有

$t_n\equiv (a{S}_n+b)-(a{s}_{n-1}+b)\equiv a{t}_{n-1}\mathrm{mod}m$

$t_{n+1}{t}_{n-1}-t_n^2\equiv (aa{t}_{n-1}{t}_{n-1}-a{t}_{n-1}a{t}_{n-1})\equiv 0\mathrm{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_n{t}_{n-2}-t_{n-1}^2))$