随机数是如何生成的

本文主要介绍随机数的概念与分类,以及简单的统计学伪随机数算法。

1. 随机数概念

这里我们主要讨论的是密码学范畴的随机数。随机数的随机性检验可以分为三个标准:

  1. 统计学伪随机性。在给定的随机比特流样本中,1 的数量大致等于 0 的数量。也就是说,如果我们把一个(包含足够多随机数的)随机序列里的每个随机数数转化为二进制数,并首尾相接形成一个串,那么这个串中的 1 和 0 的数量应该大致相等。满足这类要求的数字,人类“一眼看上去”是随机的。
  2. 密码学安全伪随机性。给定一定长度的随机序列,在多项式时间内演算出随机序列的任何部分的概率低于 50%。例如即使给定随机序列的前 100 个随机数,也无法在有效地算出第 101 个随机数是什么。这样的伪随机数序列难以被预测。
  3. 真随机性。随机序列不可重现。也就是说,给定相同的参数,多次计算出的结果是不同的。由于计算机算法都具备确定性的特征,因此真随机数无法通过算法生成。

相应的,随机数被分为三类:

  1. 统计学伪随机数。仅符合第一个标准的随机数。也就是只是人类“一眼看上去”觉得随机而已。
  2. 密码学安全的伪随机数。符合前两个标准的的随机数,也就是说不仅人类觉得随机,而且随机序列难以预测。这种随机数可以通过密码学安全伪随机数生成器( CSPRNG )计算得出。
  3. 真随机数。同时符合三个条件的随机数,主流观点认为只有通过量子力学的内禀随机性生成的随机数才是真随机数。

2. 统计学伪随机数算法

2.1. 平方取中法 Middle-square method

算法描述

该方法由冯 · 诺伊曼在 1946 年提出,算法非常简单:

  1. 选择一个 m 位数 $N_i$ 作为种子
  2. 计算 $N_i^2$
  3. 若 $N_i^2$ 不足 2m 位,在前补 0。选择这个数中间 m 个位的数,即 $10^{\lfloor m/2 \rfloor}$ 至 $10^{\lfloor m/2 \rfloor + m}$ 的数,将结果作为 $N_{i+1}$。

以 675248 为种子为例,675248 的平方为 455959861504,最后取最中间的 6 位数字作为结果:959861。

1539444972231

简单实现

Python 实现如下:

1
2
3
4
5
6
7
seed = '675248'
def middleSquare():
global seed
length = len(seed)
square = int(seed) * int(seed)
seed = str(square).zfill(length * 2)[int(length / 2):int(length / 2) + length]
return int(seed)

体验

See the Pen BGJxVE by Andie (@Andiedie) on CodePen.

问题

  • 总体周期过短。对于 n 位数的种子,它的循环周期总是小于等于 $8^n$。
  • 如果中间 n 位都是零,接下来就会永远输出 0。
  • 如果种子的前半部分为 0,那么后续的随机序列很快就会变成 0。你可以尝试在上面的 Seed 位置填入0099,并点击多次 Get Next
  • 随机队列卡住不变。例如当种子是 0100、2500、3792、7600 时,随机序列将永远不会改变。而这只是四位数种子时的情况。
  • 一些特殊的序列还会产生极短的周期。例如 0540 -> 2916 -> 5030 -> 3009。事实上,00 ~ 99 这 100 个二位数种子,没有任何一个周期可以超过 14。

2.2. 线性同余方法 Linear congruential generator

算法描述

线性同于方法(简称 LCG ),原理如下:

$X_{n+1}= (aX_n+c) \mod m$

其中:

  • $m$ 是模数,$m > 0$
  • $a$ 是乘数,$0 < a < m$
  • $c$ 是增量,$0 \le c < m$
  • $X_0$ 是种子,$0 \le X_0 < m$

线性同余方法就通过不断计算该式子,递推地算出随机序列。

需要注意的是,LCG 对参数的选择极其敏感。好的参数选择,可以使 LCG 产生的随机数队列序列拥有很长的周期,解决上述平方取中法的缺陷。但是糟糕的参数选择也会使得 LCG 的表现非常差。

一些常用的参数:

来源 模数 $m$ 乘数 $a$ 增量 $c$
C++11 的 minstd_rand0 $2^{31}-1$ 16807 0
C++11 的 minstd_rand $2^{31}-1$ 48271 0
Java 的 java.util.Random $2^{48}$ 25214903917 11

要注意的是,LCG 并不总是将计算结果的全部二进制位都作为输出。比如 Java 在每次迭代中使用 48 位进行计算,但是只返回结果中的 32 个高有效位。这是因为(统计上)使用这种截断方法可以拥有更长的周期,产生更加好的随机序列。

简单实现

Python 实现如下,这里的参数使用的是与 C++11 的 minstd_rand 相同的参数

1
2
3
4
5
6
7
8
seed = 1
m = 2**31 - 1
a = 48271
c = 0
def linearCongruential():
global seed
seed = (a * seed + c) % m
return seed

体验

See the Pen 随机数-线性同余法 by Andie (@Andiedie) on CodePen.

优缺点

优点:

LCG 速度快,且非常省空间(通常只需要 32 位或者 64 位)。且当周期足够大时,LCG 甚至可以通过一些严格的统计测试。

缺点:

通过线性同余方法构建的伪随机数生成器的参数可以轻易地由其输出的随机序列演算得知,所以此种伪随机数生成器属于统计学伪随机数生成器。

此外,LCG 产生的随机序列的最大周期是模数 $m$,通常是 $2^{32}$ 左右,这对于大多数场景来说已经足够了。不过对于某些应用来说,这样的周期还不够大。

2.3. 梅森旋转算法 Mersenne twister

梅森旋转算法松本真和西村拓士在 1997 年开发,可以快速产生高质量的伪随机数,修正了古典随机数发生算法的很多缺陷,是 R、Python、Ruby、IDL、Free Pascal、PHP、Maple、MATLAB、GNU 多重精度运算库和 GSL 的默认伪随机数产生器。从 C++11 开始,C++ 也可以使用这种算法。

算法描述

目前使用最广泛的是 MT19937,可以产生 32 位的整数序列。整个算法主要分为三个阶段:

  1. 初始化:根据种子生成初始状态。
  2. 迭代:迭代产生下一个状态。
  3. 提取:从当前状态中提取随机数。

简单实现

Python 实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class MT19937:
def __init__(self, seed = 0):
self.state = [0] * 624
self.index = 0
self.state[0] = seed
for i in range(1, 624):
self.state[i] = (0x6c078965 * (self.state[i - 1] ^ (self.state[i - 1] >> 30)) + i) & 0xffffffff

def generate_numbers(self):
for i in range(624):
y = (self.state[i] & 0x80000000) + (self.state[(i + 1) % 624] & 0x7fffffff)
self.state[i] = self.state[(i + 397) % 624] ^ (y >> 1)
if y % 2:
self.state[i] = self.state[i] ^ 0x9908b0df

def extract_number(self):
if self.index == 0:
self.generate_numbers()
y = self.state[self.index]
y ^= y >> 11
y ^= (y << 7) & 0x9d2c5680
y ^= (y << 15) & 0xefc60000
y ^= y >> 18
self.index = (self.index + 1) % 624
return y

体验

See the Pen BGJxvg by Andie (@Andiedie) on CodePen.

优缺点

优点:

  • 周期非常长,MT19973 的周期可以达到 $2^{19973} - 1$。
  • 均匀性好。
  • 速度非常快,基本都是位运算。

缺点:

  • 空间成本高,需要 2.5 KB 的缓存空间。(之后原作者又推出了仅占用 127 bits 的 TinyMT )
  • 不是密码学安全的伪随机数生成器。由于提取函数是可逆的位运算,暴露了内部状态,因此梅森旋转算法是可以爆破的。

参考