线性同余发生器是当前应用比较多的一种随机数发生器，其简称为LCG（Linear Congruence Generator)或者也叫做LCG方法。于1951年由Lehmer提出，也被称作同余发生器，因为它是利用的同余的算法来计算的，是目前使用的比较多的一种方法。文献综述

同余与线性同余法

有整数；为模并，若b-a为M的倍数，则有a,b同时除以M后所得余数相同。则称为a与b关于模M同余，记为。

同余具有以下性质：

① 对称性：若，则。

② 传递性：若，，则。

③ 若，则，。

④ 若，则，其中（M,C）表示M和C的最大公因子。

LCG方法的一般递推公式为

其中M为模数，a为乘数，c为增量，且Xn，M,a,c均为正整数（包括0）。       

显然由（1。1）式所得的满足：，从而，应用递推公式时式中参数a,c,X0,M的选取是均匀随机数产生的关键。

例3。5 取，利用（1。1）式得到数列为：6,9,0,7,6,9,0,7，。。。

易见，且从n=5开始到n=8，我们将得到与n=1到n=4完全相同的（及），顺序也完全相同，T=4称为数列的周期。

运用同余法产生的数列中重复数之间最短的循环长度称为该初值下LCG的周期，记为T，如果满足T=M，称为满周期。

例3。6   取，利用（1。1）式得到的数列为：21，41,13,1,5,25,61,49,53,9,45,33,37,57,29,17,21，。。。，数列的周期T=16＜M。

例如   取，利用（1。1）式得到数列为：6,1,8,11,10,5,12,15,14,9,0,3,2,13,4,7,6,1，。。。，数列的周期Y=16=M，故称由以上参数决定的LCG具有满周期。

易知，只有适当选取参数及M，才能得到周期长并且均匀性，随机性好的数列。

混合同余法（混合式LCG）来.自^优+尔-论,文:网www.chuibin.com +QQ752018766-

当（1。1）式中满足条件参数c＞0，那么该LCG方法也被称为混合同余法，或者称为混合式LCG。如例3。6就是混合同余式发生器，但参数选取的不好，使得所产生数列的周期T＜M，且随机性差，以下讨论如何选取，使得所得混合发生器为满周期。

    满周期混合式LCG中的选取准则

    定理1。1  如果下列三个条件都满足，由（1。1）式定义的LCG可达到满周期

      ① c与M互素（即可以同时整除c和M的正整数只有1）；

      ② 对M的任一个素因子P，（即a-1应被P整除）；

      ③ 如果4是M的因子，则。

定理（1。1）给出了混合式LCG取到满周期时应满足的条件。经常取，其中L是计算机中存放一个整数值的二进制位数（称为整数的尾数字长）。这种取法有两个优点：第一是可以通过适当选取参数，使周期变大甚至达到满周期；二是可以精简计算[6]。