关于随机数的产生方式初探


人是人他妈生的,妖是妖他妈生的.   近日对随机数是怎么生出来的这个命题有了兴趣。这是由于对hash函数分析时,发现它与随机数生成也有某种关系。故尔遂作探讨。学过数论的人就免看了。难入法眼。本文是上班期间草就，语句不通的地方凑和看。 意思就那么个意思。

本文主要讨论，我们为什么都被random()被期骗了！ 伪随机数给人造成真随机的错觉！

如果种子(也就是公式里的Xn在n=0时,即第一项X0)不变，random()是有周期性的！ 过段时间会完全再现！
（当然要看random()采用什么算法了！ 如果是采用线性同余——这是最流行的，总会这样！！）

应用最广的随机数生成算法是由Derrick Henry Lehmer1951年给出的线性同余法：

              Xn+1 = ( aXn + c ) mod m,  n>=0.

此式称为线性同余随机数生成算法。由于俺数学水平太差，就用这个最简单、最普遍的用例进行研究。
人们研究发现c对随机效果影响不大, 一般为了提高计算速度，令c=0,其公式可写为
           r[i+1]=(a*r[i]) mod m

这是一种迭代公式.每次算新的数时,都把上次生成的数放进去. 用计算机语言函数来写，就是

int r=r0;//这一项相当于种子函数,例如vc的srand()或delphi的randomize()
int Rand(int range)
{
  r=(a*r)%range;
  return r;
}

上式中，r是一个全局变量。r的初值r0称为种子。

从这个定义出发去试，对于比较小的a,m，很容易发现有两种典型现象：
现象一：重复循环现象。 如下
a=7 r0=2 m=10
4
8
6
2
4
8
6
2
4
8
6
2

现象二：死循环现象。如下
a=7 r0=5 m=10
5
5
5
5
5
5
5
5
5
5

仔细分析后，发现以上两种现象其实容易理解：

为叙述方便，把上面的公式改写一下:

r2=(a*r1)%m;   ------- [1]

性质：根据取余的定义，[1]式的值域是有限的，其输出值 r2为0,1,2,....m-1

由此，可知

定理一：种子r0确定后，从公式[1]一直递推，必然导致循环。

证明：由于公式是死的，所以r1一定，必然产生固定的r2,这个r2又会产生r3
   r0-->r1-->r2-->r3.....rn-->rn+1....

(反证法)如果永不循环，就意味着有下面两种情况：

永不循环情况1：
不断有新数出现。意味着有无穷多个新数进入这个序列。 这是不可能的。因为该公式的值域只有0...m-1 总共m个整数。

永不循环情况2：
在这个序列中，不断有新的上下文之间组合出现。以至从不循环。这是不可能的。因为从r1到rn，都没有自由度，有了Rn，就直接决定了Rn+1。 由于这种决定性关系，排斥了随机组合顺序,每个数的上下文都是固定的,不可能出现新花样。由于这种递推关系，每一个新诞生的数都必须与上一个数不同，才能不导致循环。 由于总共只有0到m-1（m个数），所以这个不循环的序列不可能一直这样下去。当这个序列长度超过m，就必然出现重复出现0..m-1中某个数字。 而且只要这个数字出现第二次，由于递推公式没有变化，递推出来的数字序列就会再次重演，就意味着进入了循环。所以，那么R1到Rn如果没有出现循环，那么它的长度不可能超过m。 并且，如果m不是质数，一般都会在序列总长度还没到m的时候，中途就遭遇某个重复数字进入循环。

推论1：公式[1]的循环周期<m

推论2：m为质数时，序列循环长度为m-1，从1到m-1每个数都会遍历。
这个利用了质数一个特性，就是从1到m-1，没有一个数会是m的因子。避免了序列中途夭折。具体原因挺费解，涉及互质、最小公倍数、同余等数学概念。在此就不说了，自己去悟。你想想高中时物理测量纸厚度用过的千分尺，就是借助了9，10互质这种特性。每次刻度差1，每相差10为一轮。如下：
a=7 r0=5 m=11
2
3
10
4
6
9
8
1
7
5
2
3
10
4
6
9
8
1
7
5
2

定理二：单项死循环，要么一开始就是（即r2==r1)，要么永远不会出现。不可能出现若干个不同的数之后，突然进入同一个数的情况。
这个由公式[1]的递推决定性可以推层出来。因为如果输入和输出是同一个数，比如5==(7*5)%10这种情况，你再把输出放进去出来还是同一个数。进入死循环。
一种特殊情况是，r0=0或r0=m时，r1总是为0，会进入全0。 所以r0应取1到m-1之间

结论：这个线性同余公式，其实是很差的。这个公式甚至不能确保每个周期中每一个数都至少出现一次这个条件。只是给人一种错觉，大致上看数字“随机”出现。这种随机感觉其实是由于递推和mod带来的。如果你猜不中a，就难以推测这种出现顺序。

另一方面，产生随机数的一需要仔细调节参数，才能达到某种更好效果。每次都用不同的种子。精心调节a,m值(a,m互质时,该公式会"随机"遍历从0至m-1每个数)，或用更好算法。所以称为伪随机。

那用过delphi的人会说,我平时用的randdom()函数,也没见有重复啊? 即便随机范围为2(只取0,1)??? 哦,我想是这样的,写rand()函数的人不可能直接你给range为多少,我把m就取多少. 可以在内部定一个很大的m,算出来后,把它折合到你的range中就行.要是我的话,我会在内部取64位的大质数m。你有本事来等着循环出现

另外, delphi和c内部的随机函数倒底用的是哪种公式,取的是什么参数. 我还没来得及看.

通过进一步摸索，发现一个秘密,一般人我不告诉他。：）

发现各种随机算法和hash算法,都与一部特别牛的巨著三卷本《计算机程序设计艺术》有关系。这个书名起得很俗，但里面的内容真是.....怎么说呢？ 非常变态! 全是泰勒级数展开等数学公式。还有巨多困难习题。只有相当数学功底的人才能看懂。 不过后起之秀，想一步登天的人还是值得拿来研究的。可惜该书在市面上绝版

[课程]Android-CTF解题方法汇总！