杂谈:计算机里出不来‘真随机’

z

这是一个大家或多或少都听过的名词——“伪随机”

极致省流的来讲，计算机的确定性使得计算机中不存在真正的“随机”机制

计算机的确定性

计算机是一个确定性系统，它的所有操作都是遵循预设的指令来进行的，也就是说它的输出只由输入和初始状态决定，一套输入和初始状态，只能对应一个输出值。

也正是因为这种确定性，我们才会使用计算机进行极大规模的运算而不担心它出错。

伪随机数怎么产生的

我记得刚开始上python，有一题是这么出的

随机开柜码

答案：

1
2
3
4
5
6
7
8
9
10
11
import random
def code(seed):
    random.seed(int(seed))
    lst = "ABCDEFGHIJ0123456789"
    p = ''
    for i in range(6):
        c = random.choice(lst)
        p += c
    return p
n = int(input())
print(code(n))

当时做到这里其实很疑惑的

啥叫种子啊

为什么种子是5，输出出来的就一定是"9I16A4"

豆包助我！

原来，计算机的伪随机数都是拿特定的算法产生的

接下来仔细掰扯掰扯

伪随机数生成器PRNG

先来看个简单且年龄贼大的PRNG算法——线性同余法

公式为
Xn+1=(aXn+c)mod  mX_{n+1}=(aX_n+c)\mod{m}

在这里，a、c、m都是预定义的常数

其中m为周期，也就是说生成的随机数的范围

而XnX_n就是当前状态

这里只要XnX_n有所改变，就会产生不同的随机数

而种子，就相当于X0X_0，也就是初始值，当我们预设种子seed时，当前的XnX_n也会被替换为seed，之后每次生成的随机数都会覆盖原有状态，就这样以递推的方式不断生成新的随机数

而当我们没有设置种子时，程序可能会以当前系统时间（精确到毫秒）或者其他随机熵源作为默认种子

提一嘴，梅森旋转法(Mersenne Twister)是当前PRNG的主流算法，Python自带的random模块就是默认使用该算法，这里不做详细解释

在密码学中，我们不使用普通PRNG，而使用密码学安全的随机数生成器（CSPRNG），它会引入外部熵源如系统硬件噪声、用户输入延迟等，更加随机