原创 | 随机数大家都会用，但是你知道生成随机数的算法吗？
点击上方蓝字，关注并星标，和我一起学技术。
今天我们来和大家聊聊随机数。
大家如果学过编程对于随机数应该都不陌生，应该或多或少都用到过。再不济我们每周的抽奖都是用随机数抽出来的，我们用随机数的时候，往往都会加一个前缀，说它是伪随机数，那么这个伪随机数的伪字该怎么解释，什么又是真随机数呢？
真伪随机数
目前学界划分真伪随机数的方式非常简单，一句话就能说明白，凡是用一定的算法使用程序生成的都是伪随机数，通过物理现象产生的随机数才是真随机数。也就是说计算学家们已经证明了仅仅依靠算法是无法生成真随机数的，也可以认为这是一个NP问题。
算法生成的都是伪随机数的证明太过复杂我们可以不去深究，但是什么又叫做物理现象产生的随机数呢？其实也很简单，举个很简单的例子就是抛硬币和掷骰子。当然物理现象不止这些，比如还有电子元件的噪音、元素的衰变等等。
真假随机数之间的最大差别在哪里？其实就在是否可以预测上。计算机算法得出的各种随机数之所以是伪随机数是因为它们的结果都是可以预测的，只要我们知道算法和起始状态以及各种参数，就可以预测下一次随机出来的结果。而真随机数则无法预测，就是纯粹随机的。
但问题来了，抛硬币和掷骰子这些物理现象又是真的随机吗？如果我们知道了硬币的起始状态以及抛掷的角度和力度，是不是可以预测硬币抛掷的结果呢？进一步我们是否可以假设，如果我们能知道所有例子的所有状态，是否所有所谓的随机数都是可以预测的呢？但根据量子力学的测不准原理，我们知道我们无法同时知道粒子的位置和动量，不仅说明了我们无法预测，也说明了我们无法假设预测。
所以某种程度上来说物理现象是不是就是真随机，这就成了一个哲学问题。但至少在计算机领域当中，这个问题是明确的，算法得出的都是伪随机数，只有通过物理现象得出的才是真随机数。
在计算机系统当中，伪随机数都是有周期的，只要我们持续的次数足够多，就可以看到这种周期。而真随机数则不存在这种周期，有一位前辈做过一个随机数可视化实验，也就是把随机数得到的结果做成图片。我们可以直观地对比一下，这是真随机数可视化之后的图片：
看起来像不像是以前的电视收不到信号的时候显示的内容？我们再来看看通过算法生成的伪随机数可视化之后的结果：
对比一下还是挺明显的，明显可以看出来伪随机数是有规律的，这个规律体现出来就是图像当中的纹理。如果大家想要获取真随机数，可以访问random.org这个网站，它是免费的，我们可以人为设置上下限来获取指定范围内的随机数。
对比过真伪随机数之后，我们再来看看现在计算机系统当中常用的伪随机数生成算法的原理。
平方取中法
我们首先介绍的是平方取中法，这个方法非常简单粗暴，是用来产生四位随机数的。
具体的逻辑是怎样的呢？首先我们需要一个随机种子，比如2333，我们把这个随机种子进行平方，得到5442889。这个数一共有7位，我们给它左边填充一个0变成05442889，最后取出它的中间四位是4428，这就是我们随机得到的结果。当我们下次再计算随机数的时候，随机数的种子就成了4428。
这个算法的作者是大名鼎鼎的计算机之父冯诺依曼，自从他确定了计算机体系结构之后一直沿用至今。他当时推崇这一算法的原因很简单，计算方便，速度快，也容易排查错误。它认为如果真的设计一个复杂的算法来生成看起来比较好的随机数，可能隐藏的bug比解决的问题还要多。
seed = 2333
def random():
global seed
seed = seed ** 2
return int(str(seed)[1:5])
我写了代码实际运行了一下，结果看起来其实没有那么不靠谱。
LCG算法
冯诺依曼的随机数算法虽然看起来简单，但是非常草率，在很多场合下是显然不能使用的。所以人们又想出了新的算法，这个算法也很简单，看起来英文缩写高大上，其实翻译过来是线性同余法。也就是利用 来生成随机数。
最后返回的结果是上述式子计算之后的结果，abc三个数都是我们选定的参数。当下一次随机的时候，就将上次的结果作为新的种子进行计算。我们写出它的递推公式就是：
这个算法一眼就看明白了，它的核心完全在于abc这三个参数的选择。如果选的不好就不能实现随机数的效果，这里我给大家分享一个业内常用的选择，a=25214903917，b=11，c= 。这些数不是拍脑袋随便选的，而是计算学家们算出来的。实际上Java JDK当中Random的类采用的就是这样的算法。
seed = 2
def lcg():
global seed
seed = (25214903917 * seed) & ((1 << 48) - 1)
return seed
这种算法实现方式也非常简单，并且得到的效果也不错。如果要增加随机性，我们还可以在输出结果上做一些优化，比如进行位移或者是调换二进制位的顺序等等。但是这种算法也有缺点，就是它的计算方式是固定的，只是随机种子未知。只要愿意，我们是可以通过得到的随机结果去反推这些参数的。
这并不是一个复杂的算法，因此LCG算法得到的随机数不能应用在一些高安全级别的应用上，否则可能会有安全隐患。
梅森旋转算法
LCG算法实现的伪随机数效果还不错，但是周期不够长，很容易被黑客推算出随机种子。后来两个日本学者又研究提出了新的伪随机数算法，在这个算法当中用到了梅森素数，所以称为梅森旋转算法。
简单介绍一下梅森素数，梅森素数的意思是形如 的素数。利用梅森素数的性质可以设计出周期长度为梅森素数长度的随机数周期。比如目前Python、C++11等语言当中用的随机数计算包都是用的这种算法。目前常用的版本周期是 ，这是一个巨大的天文数字。
梅森旋转算法的实现原理非常复杂，网上的资料也不多，我看过一些都不是非常好懂。这里就不介绍了，大家感兴趣可以去了解看看。但我个人觉得意义不大，因为实在是用不到，面试也完全不会考。
虽然梅森旋转算法的周期非常非常长，但是仍不是安全的随机数算法，仍然有可能会被黑客破解。只不过和LCG算法相比，被破解的概率以及难度增加了许多。
大家可能很好奇，什么样的算法才是安全的呢？其实业内的安全算法其实挺取巧的，一般的常用方法就是利用一个数学界的难题来设计一个算法。比如RSA加密算法，利用的就是大整数因式分解的问题。这样的问题业内除了暴力计算没有好方法，而暴力计算的复杂度非常非常高，根本不可能在有限时间内有解，自然这个就是一个安全的算法了。如果某位黑客有能力设计出破解的算法来，他根本也不用破解啥，只要把解法发表成论文，自然可以名利双收。
你看随机数这么一个常见的功能下面居然隐藏了这么深的科学原理，而且更加震惊的是以我们人类如此厉害的文明，居然连随机一个数都做不到。不知道大家看到这里又有何种感受呢？
今天的文章就到这里，衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话，请来一个三连支持吧~（点赞、在看、转发）
- END -
本文分享自微信公众号 - TechFlow（techflow2019）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
