随机算法线性同余法的理解

线性同余如何模拟随机算法

程序员对随机数一般都不陌生，而且众所周知，计算机中通常实现的是伪随机数列。何为伪随机数列？

伪随机数（或称伪乱数），是使用一个确定性的算法计算出来的似乎是随机的数序，因此伪随机数实际上并不随机

既然是通过算法来模拟随机过程，那什么样的算法可以达到接近随机的效果，它又是怎么实现的呢？

比较简单的一种便是线性同余法。

用线性同余法产生随机数的特点是非常容易实现，生成速度快，但是弊端也很明显，32位的数周期最长只能到 ，达不到需要高质量随机数的应用如加密应用的要求

了解这些以后，首先我脑中冒出一个疑问，为什么线性同余法可以做到模拟随机过程呢？所谓随机就是任何数字都有可能出现，也即所有数据出现是等概率的，符合均匀分布。那线性同余法是如何做到均匀分布的线性同余法是如何做到均匀分布的？

第一步我们需要理解线性同余的周期，上述定义中有清晰的说明，对取模M的线性同余产生的序列周期最大为M。设想下假设递推公式为 , 若周期为T，则 , 由于 , 也就是说唯一的 决定唯一的 , 那么T必小于等于M，因为取模M共有M个不同的整数结果，第M+1个数一定和前面某一个数相同，而由于一一对应的递推关系，后面的序列也会依次与前面的数相同，最后必有周期T<=M。

其次乘积系数与取模最好互质，这个其实也比较好理解，仍以 为例，若A与M不互质，那假设 ， ，其中 。扩展递推公式为 ，由于B为常数，可以当做一个偏移量，使两边都减去B，变换递推公式为 ，这样可以很容易推知对所有的 均含有d这个因子，以 为例，序列中原有的M个可能数字在循环中只能取到偶数值加偏移量B，也就意味着周期T<=M/2，这便破坏了整个序列的均匀分布。举几个简单的例子帮助理解，假设现在A=3，M=5，令 ，序列为{2，1，3，4，2，1....}周期为5，若取A=6，M=10，令 ，序列为{2，2，2....}周期为1

对应的其他条件，同样是为了确保整个序列周期为M。详细推导过于复杂，有想要了解的，建议参考这篇论文：

回到最初的疑问，线性同余法是如何做到均匀分布的。从上面我们可以得知，通过特定条件的参数选择，我们可以构造一个序列周期为M，且M的周期中各数字只出现一次，因此在整个序列中，各数字出现的频率是相同的，也就符合了均匀分布。

线性同余方程如何求解

明白随机分布与线性同余的关系后，我们扩展一下知识，来了解下线性同余方程的解法。这不仅仅是一个纯数学问题，它实际上有很多应用的例子，比如：

在一个圆环上有两只青蛙A和B，从0点自东向西为正方向，两只青蛙的位置分别为x,y，A每次跳m,B每次跳n，环总长为L.两只青蛙同时出发，两只青蛙落在同一点视为相遇，问最少经过几次跳跃两只青蛙相遇。

根据条件，我们列出解题方程： 其中≡代表两边取模

展开为

平移后转换为 即

令 , 可得 ,这便形如标准的一元线性同余方程

定义:a,b是整数，形如 ，且x是未知整数的同余式称为一元线性同余方程，其中≡ 及(mod M)表示两边对M取模

求解一元线性同余方程，首先需要将其一步步做如下变换：

1. 标准的一元线性同余方程 等价于
2. 假设d为a与M的最大公约数，记为 ,易知若x，y有解d必为b的因子，因此等式变换为 其中 , , ,且 互质，即
3. 令 方程变换为 即

最后运用模逆计算出

定理：如果a和M为互素的整数，M>1，则存在a的模M的逆.而且这个逆模M是唯一.

这个定理的证明也比较简单，推导过程如下：

若a与m互质，必存在 （若a,M有大于1的公因子d，则 而不可能等于1），两边取M的模，可得 ,即s为a的模M的逆

若记 为a的模M的逆，即 ,也就是

举个简单的例子：

求解

1. 由于 ,可知存在5模9的逆，易知
2. 得出2为5模9的逆，方程两边乘以2有
3. 化简为
4. 得出

综合以上，我们将普通线性同余方程 转换为标准方程 进行求解，求解标准方程完毕后需要将解空间映射回去，若标准方程的解为

则由于 且 ，得出 为方程 的解

至此，我们缕清楚了一元线性同余方程的求解过程，也对线性同余法有了更深的了解，基于以上知识，再回归去看程序求解线性同余的扩展欧几里得算法，就比较好理解了。 但是线性同余法只是随机算法中最简单的一种，可想而知其他可能看似简单的算法实际都有深挖的价值。

PS：以前经常听人提起数学无用论，什么这个定理那个法则在实际中都没有用处，计算机行业中也不乏有这样的声音。但是现在逐渐发现如果你的工作中用不到这些看似深奥的理论，你就可以想想是不是你的工作本身或对工作的了解还不够有深度。因此仅以此文自勉，希望之后自己工作可以逐步做深做精。

参考链接：