1.啥是伪随机啥是真随机
就像伪摇滚、伪球迷一样,伪随机沾上了主观的“伪”字,就有很多种定义方法。在介绍这些方法之前,先看一下产生随机有哪几种。
①固定种子、固定公式的随机数序列
举个例子,我首先拿出一个数X,然后每次对X使用公式 (3X + 4) % 5,再把结果给回X(%指的是求除法的余数)。假设X初始值是0,那么生成的“随机数序列”就是4, 1, 2, 0, 4, 1, 2, 0, 4, 1, 2, 0...
这就是一个非常简单的随机数生成器了。而X的初始值被称为“种子”。
但是大家很快就会发现问题,它循环了。4,1,2,0的循环体系使的人们在充分观察之后,可以发现规律并预测出下一个“随机数”。
这个问题其实也好解决,3,4,5都是太小的数了,我把3,4,5都搞的非常大,循环周期就将会非常长,使的没有任何能看出它其实是循环的。比如在C++的函数库MT19937中,循环周期达到了2^19937-1这么长,基本遍历一整个宇宙的时间都无法重复。
②随机种子、固定公式的随机数序列
上一个例子中,虽然算法(至少表面上)解决了循环的问题,但还有一个问题,那就是每次的结果都是固定的。两次使用同一个公式和种子,得到的结果是完全相同的,这可太不随机了。怎么办?
解法就是改变种子。如果种子改变了,那么之后的序列就完全不相同,随机的目的就达到了。那么,改变种子该依据什么呢?如果还是使用公式生成,那这个生成随机种子的公式又该用什么随机种子呢?(有点绕,大家可以仔细思考一下)
一个很好的办法是放弃数学上的公式,改为使用物理特征,比如,时间。如果我使用从1970.1.1至今的秒数作为初始种子,这总不太可能重复了吧?如果大家写过C语言,很可能接触过这行指令:srand(time(0)),它的作用就是上述的种子初始化。
当然,用时间作为种子在安全上也不是万无一失的。我以前搞信息安全的时候,遇到过以时间为种子的攻击方式,思路是先算出来当前的秒数,然后预测代码会什么时候执行,根据执行时间配合随机种子达成攻击。扯远了,不多说了。我的意思是,如果嫌时间都不安全的话,还可以使用“当前CPU的温度”、“当前内存剩余量的字节数”等等无法探测的物理硬件特征作为种子,使得种子完全随机、安全。
③随机种子、随机公式的随机数序列
总的来说就是在X = (aX + b) % c的公式中,改变每次的X时同时依据X的值改变a,b,c。但是这样的问题在于,如果X不改变,两次的模拟结果仍然是完全相同的。所以这种方法现在用的不多,只作为提一句而已。
④现实中的随机
截止到③,已经基本是计算机模拟随机的极限了。再往上无非是把公式搞得更复杂一些,用“异或”运算代替乘法之类的,换汤不换药。
那么现实中的随机是什么样的呢?现代物理学的解释是:量子力学。
就算大家没学过量子力学,应该也多少听过薛定谔的猫、量子纠缠、海森堡测不准原理等名词。从名字就能看出,测都测不准,当然是最高级的随机了。这部分是完全没有公式的真·随机
当然这部分涉及最尖端的量子物理,我没法讲的很深入,有大学物理基础且有兴趣的同学可以去看下隐变量猜想。贝尔证明了,如果真的有隐变量,那么物理定律的定域性和实在性起码必舍其一,而因为实验和物理学家都不愿意否定这两点,所以现在物理学界认为是真随机。
就像伪摇滚、伪球迷一样,伪随机沾上了主观的“伪”字,就有很多种定义方法。在介绍这些方法之前,先看一下产生随机有哪几种。
①固定种子、固定公式的随机数序列
举个例子,我首先拿出一个数X,然后每次对X使用公式 (3X + 4) % 5,再把结果给回X(%指的是求除法的余数)。假设X初始值是0,那么生成的“随机数序列”就是4, 1, 2, 0, 4, 1, 2, 0, 4, 1, 2, 0...
这就是一个非常简单的随机数生成器了。而X的初始值被称为“种子”。
但是大家很快就会发现问题,它循环了。4,1,2,0的循环体系使的人们在充分观察之后,可以发现规律并预测出下一个“随机数”。
这个问题其实也好解决,3,4,5都是太小的数了,我把3,4,5都搞的非常大,循环周期就将会非常长,使的没有任何能看出它其实是循环的。比如在C++的函数库MT19937中,循环周期达到了2^19937-1这么长,基本遍历一整个宇宙的时间都无法重复。
②随机种子、固定公式的随机数序列
上一个例子中,虽然算法(至少表面上)解决了循环的问题,但还有一个问题,那就是每次的结果都是固定的。两次使用同一个公式和种子,得到的结果是完全相同的,这可太不随机了。怎么办?
解法就是改变种子。如果种子改变了,那么之后的序列就完全不相同,随机的目的就达到了。那么,改变种子该依据什么呢?如果还是使用公式生成,那这个生成随机种子的公式又该用什么随机种子呢?(有点绕,大家可以仔细思考一下)
一个很好的办法是放弃数学上的公式,改为使用物理特征,比如,时间。如果我使用从1970.1.1至今的秒数作为初始种子,这总不太可能重复了吧?如果大家写过C语言,很可能接触过这行指令:srand(time(0)),它的作用就是上述的种子初始化。
当然,用时间作为种子在安全上也不是万无一失的。我以前搞信息安全的时候,遇到过以时间为种子的攻击方式,思路是先算出来当前的秒数,然后预测代码会什么时候执行,根据执行时间配合随机种子达成攻击。扯远了,不多说了。我的意思是,如果嫌时间都不安全的话,还可以使用“当前CPU的温度”、“当前内存剩余量的字节数”等等无法探测的物理硬件特征作为种子,使得种子完全随机、安全。
③随机种子、随机公式的随机数序列
总的来说就是在X = (aX + b) % c的公式中,改变每次的X时同时依据X的值改变a,b,c。但是这样的问题在于,如果X不改变,两次的模拟结果仍然是完全相同的。所以这种方法现在用的不多,只作为提一句而已。
④现实中的随机
截止到③,已经基本是计算机模拟随机的极限了。再往上无非是把公式搞得更复杂一些,用“异或”运算代替乘法之类的,换汤不换药。
那么现实中的随机是什么样的呢?现代物理学的解释是:量子力学。
就算大家没学过量子力学,应该也多少听过薛定谔的猫、量子纠缠、海森堡测不准原理等名词。从名字就能看出,测都测不准,当然是最高级的随机了。这部分是完全没有公式的真·随机
当然这部分涉及最尖端的量子物理,我没法讲的很深入,有大学物理基础且有兴趣的同学可以去看下隐变量猜想。贝尔证明了,如果真的有隐变量,那么物理定律的定域性和实在性起码必舍其一,而因为实验和物理学家都不愿意否定这两点,所以现在物理学界认为是真随机。










