第二季 · 第 33 章

计算机如何掷骰子

《算法的故事》第二季 · 第一篇：数学家的秘密武器——冯·诺依曼与伪随机数的诞生

1940年代末，美国。电子计算机正在改变科学家处理数学问题的方式。曾经需要数十名计算员花费数周才能完成的庞大计算，现在可以交给电子线路自动执行。然而，当研究人员试图让机器模拟粒子在物质中的运动时，他们发现了一个奇怪的困难。计算机擅长执行精确的数学规则。但科学家偏偏需要一种完全不同的东西：偶然性。一个粒子下一次会朝哪个方向散射？一枚硬币究竟落在哪一面？一次复杂的物理过程将沿着哪条路径发展？如果每一步都被事先写死，模拟便失去了原本想研究的不确定性。可是，计算机终究是一台严格执行指令的机器。给它相同的初始条件，运行相同的程序，就应该得到相同的结果。那么，怎样让一台完全确定的机器，产生看上去无法预测的数字？这项任务来到了数学家约翰·冯·诺依曼面前。他提出的方法简单得令人惊讶：取一个数字，将它平方，然后从结果的中间截取几位数字，再重复这个过程。它曾经为早期随机计算提供了一条可行的探索道路。但在一些情况下，这套方法会突然陷入循环，甚至永远输出零。一台被要求制造偶然性的机器，最终却发现自己被数学规律牢牢困住。这就是伪随机数的故事。

第一幕：一台永远不会意外的机器

ENIAC 电子计算机及早期编程人员的历史照片。1946年2月，ENIAC 正式向公众展示，成为电子计算史的重要里程碑。1946年2月，宾夕法尼亚大学。美国陆军与宾夕法尼亚大学共同开发的一台大型电子计算机，向公众展示了它的计算能力。这台机器叫作 ENIAC。在那个年代，它的体积大得惊人。机器由大量电子管、电缆、开关和计算单元组成，占据了很大的房间。操作人员通过复杂的接线和设置，使机器执行预定的运算。对于习惯了智能手机的人来说，这样的设备似乎既笨重又原始。但是在当时，它代表着一种划时代的能力：人类第一次拥有了一类能够以电子速度自动执行庞大数值计算的通用机器。过去，弹道计算、数值积分和复杂的数学表格制作，需要依靠人力和机械计算设备。现在，电子计算机可以把其中许多重复步骤自动完成。然而，计算速度的提高带来了一个新的矛盾。

世界并不总是按照唯一的道路前进

假设科学家要研究一束中子穿过某种物质时会发生什么。某个中子可能穿过一段距离而没有发生碰撞。也可能撞到原子核。碰撞之后，它可能改变方向、损失能量、被吸收，或者引发其他反应。研究人员关心的是：当无数这样的过程不断发生时，整个系统呈现怎样的统计规律？直接求解全部复杂过程，可能非常困难。于是，人们希望通过大量模拟来逼近结果。让计算机模拟一个中子。再模拟第二个。第三个。第四个。直到得到足够多的样本，从而估计整体行为。可是，每一次模拟都需要面对一个问题。在某个具有不同可能结果的事件中，到底应该选择哪一种结果？如果程序每次都选择同一个方向，那么所有模拟都会沿着同一条路径重复。这无法代表我们想要研究的随机过程。计算机需要掷骰子。但它没有手。没有骰子。甚至没有真正意义上的“随便选一个”。它只会执行程序员给出的指令。

图33-1：同一个起点，两种不同的计算

查看 SVG 配图原件

33-003-8512e7a84f95.svg · 点击查看大图

教学示意。真正的随机模拟不仅要得到不同结果，还必须让结果符合所研究的概率模型。

蒙特卡洛方法遇见了电子计算机

第二季下一章将详细讲述蒙特卡洛方法的诞生。但它与本章的联系，需要先说明。在1940年代，洛斯阿拉莫斯实验室的研究人员开始系统探索如何通过随机抽样解决复杂的物理计算问题。其中包括斯坦尼斯瓦夫·乌拉姆（Stanislaw Ulam）、约翰·冯·诺依曼（John von Neumann）、罗伯特·里希特迈尔（Robert Richtmyer）和尼古拉斯·梅特罗波利斯（Nicholas Metropolis）等人。1947年，利用 ENIAC 开展蒙特卡洛模拟的计划逐渐成形。这不是一个人独自在实验室里完成的工作。根据计算机史研究，约翰·冯·诺依曼、克拉拉·冯·诺依曼（Klara von Neumann）以及阿黛尔·戈德斯坦（Adele Goldstine）等人，在把模拟思想转化为实际计算程序的过程中都发挥了重要作用。^{[Oxford Academic]}克拉拉与阿黛尔的工作提醒我们：计算机史不仅属于提出数学思想的人，也属于把想法变成可靠程序的工程师和程序员。而这一时期的大规模模拟，带来了一项新的基础需求。科学家不再只需要几十个随机数字。他们可能需要成千上万，乃至更多的随机数字。最关键的是，这些数字必须足够可靠。因为只要随机数本身存在严重缺陷，再精确的物理模型也可能产生错误的统计结果。这就像使用一副作弊的骰子进行实验。即使记录每一次投掷都没有错误，最后得到的概率也可能偏离真实情况。计算机不仅需要随机数，而且需要有足够质量的随机数。这个要求，看起来与计算机的确定性天生矛盾。然而，冯·诺依曼发现，或许可以先放弃“真正不可预测”这个严格目标。只要求生成的数字序列，在统计表现上足够接近我们需要的随机样本。如此一来，问题就出现了转机。

第二幕：冯·诺依曼的大胆想法——让数字自己制造数字

约翰·冯·诺依曼（1903—1957），二十世纪重要数学家，在计算机设计、数值计算、博弈论等领域都有深远贡献。冯·诺依曼1903年出生于布达佩斯。他很早便表现出出众的数学能力。后来，他在欧洲从事数学研究，并于1930年代进入美国普林斯顿高等研究院。他的研究横跨多个领域。纯粹数学、量子力学、数值分析、经济学中的博弈论、计算机体系结构……对于冯·诺依曼而言，这些看起来差别很大的问题，常常可以通过数学结构建立联系。在电子计算机诞生的早期，他也深入参与了高速数值计算的研究。

数字真的必须来自偶然事件吗？

想象这样一个场景。你希望产生一串数字：4821，0375，9164，2208……这些数字看上去没有明显规律。假设有人告诉你，它们全部是由一个固定公式生成的。你可能会感到奇怪。既然有公式，怎么还能叫随机？这正是问题的核心。如果一段数字序列严格由初始值和固定规则决定，那么在数学意义上，它并不具备真正的独立随机性。但如果观察者不知道生成规则或初始状态，数字在表面上仍然可能表现得非常复杂。例如，数字0到9出现的频率可能接近相等。连续数字之间可能没有容易发现的规律。在某些模拟计算中，这样的序列或许已经能够满足要求。由确定性算法生成、用于模拟随机行为的数字序列，就被称为伪随机数序列。这里的“伪”，并不意味着它一定很差。它意味着序列背后的机制仍然是确定的。真正需要判断的是：它在目标应用中，是否具备足够好的统计性质。

一份真实的历史记录

1951年，冯·诺依曼关于随机数字生成方法的发言内容被整理发表，题为：Various Techniques Used in Connection with Random Digits中文可译为《与随机数字有关的若干技术》。这份文献由 George Forsythe 整理，收入美国国家标准局的应用数学资料。其中有一段非常著名的表述。冯·诺依曼把利用算术方法产生随机数字比作一种“罪过”，借此强调：严格的算术程序终究是确定性的。这段话包含着鲜明的数学幽默。他并不是在劝阻所有研究人员使用伪随机数。恰恰相反，他在同一篇讨论中，认真分析了生成、测试和使用此类数字的方法。^{[MCNP网站][国立国会図書館]}

冯·诺依曼《与随机数字有关的若干技术》文献，后收入其文集。文章讨论了物理随机源、算术生成方法、统计检验，以及中平方法可能陷入零和短循环的问题。这项研究中最广为人知的，是一个看起来近乎朴素的数字生成规则。中平方法（Middle-Square Method）。在冯·诺依曼讨论的形式中，可以使用十位十进制数字；为了便于我们亲手计算，下面采用四位数字的教学版本。

把一个数平方，再从中间取出四位

假设初始数字是：

x_0=1234

先计算平方：

1234^2=1\,522\,756

我们把结果补齐成八位数字：

图33-2：中平方法的第一步

取中间四位数字

5227

下一次运算的输入

中间四位是：

x_1=5227

接下来：

5227^2=27\,321\,529

从八位结果中继续取出中间四位：

x_2=3215

然后：

3215^2=10\,336\,225

中间四位为：

x_3=3362

如此反复。

由1234开始的一段数字序列

1234

5227

3215

3362

3030

1809

2724

4201

所有数字都由前一个数字平方后截取中间四位得到。它们并非独立抽样。

在不熟悉生成规则的人眼里，这些数字或许确实显得很混乱。它们没有简单的等差关系。也没有明显的等比关系。某些数字突然变大。某些数字又突然变小。似乎一切都毫无规律。而计算机只需要一种非常简单的操作，就能不断产生新的数字。平方。截取。重复。在当时的计算条件下，这种方法具有直观的吸引力。但就在这里，整个故事开始出现转折。这项简单而优雅的方法，内部隐藏着一个危险的陷阱。

第三幕：数字的陷阱——一台计算机突然忘记了如何随机

二十世纪中期的电子计算机实验室。早期计算需要格外重视机器故障、数值误差和计算结果的可靠性。图片为时代背景，并非中平方法某次故障的现场记录。现在，我们已经知道中平方法怎样产生新数字。但我们还没有回答一个关键问题。这种方法真的可靠吗？假如科学家让它产生一百万个数字，这些数字是否足够多样？我们来尝试一个特别的初始值。

x_0=1000

根据中平方法：

1000^2=1\,000\,000

补成八位：

01\,0000\,00

中间四位恰好是：

x_1=0000

接下来：

0000^2=00000000

再取中间四位，依然是0000。于是：

1000\rightarrow0000\rightarrow0000\rightarrow\cdots

算法从此陷入了一个无法逃脱的状态。无论运行多少次，它都只会产生零。

一颗不会转动的骰子

想象你设计了一台自动骰子机。你希望它每秒掷出一个数字。最初，它可能给出3、5、2、6……但是某一刻，它突然开始重复输出1。一分钟之后，仍然是1。一小时之后，还是1。这时，你当然不会把它当成一台可靠的骰子机。中平方法也存在类似的危险。更有趣的是，并非只有零才可能让算法停止变化。试试另一个初始值：

x_0=2500

它的平方是：

2500^2=6\,250\,000

补成八位：

06\,2500\,00

取中间四位，得到的竟然还是2500。于是：

2500\rightarrow2500\rightarrow2500\rightarrow\cdots

这个数字就像落进了自己的倒影。下一次平方，它仍然回到原处。数学家将这种情况称作不动点（Fixed Point）。对于一个迭代函数

f

，如果某个输入满足：

f(x)=x

那么继续反复应用这个函数，结果将永远不变。中平方法中的2500，便是这个四位数教学版本的一个不动点。

比不动点更隐蔽的危险：短循环

如果一个数字会产生不同的下一个数字，我们是否就可以放心？还不行。来看6100。

6100^2=37\,210\,000

中间四位是2100。接着：

2100^2=4\,410\,000

补零后取中间四位，得到4100。然后：

4100^2=16\,810\,000

得到8100。最后：

8100^2=65\,610\,000

中间四位，又回到了6100。

图33-3：一个无法逃出的四数字循环

查看 SVG 配图原件

33-007-6db99f9bc3c3.svg · 点击查看大图

4位中平方法，种子6100所形成的长度为4的循环。这一结果可以直接通过整数平方验证。

这意味着：假设我们从6100开始生成一百万个数字。最终真正参与循环的，只有四个不同的值。一百万个输出看似很多，但其中绝大多数只是重复。这样的序列，显然不适合需要大量独立随机样本的计算。

为什么这种悲剧是必然可能发生的？

这里藏着一个非常漂亮的数学结论。四位中平方法每次只保留四位十进制数字。因此，它的内部状态最多只有：

10^4=10000

种。从0000一直到9999。而每一个状态，都只能按照固定规则产生唯一的下一个状态。我们可以把它想象成一张地图。地图上有10000个房间。每个房间只存在一扇单向出口。只要你进入某个房间，下一次就一定会进入由该出口指定的另一个房间。现在假设，你不断穿过房间。经过足够多步之后，必然会再次进入某个曾经到过的房间。原因很简单：房间只有10000个，但你可以尝试走10001步、10002步……根据鸽巢原理，不可能永远进入从未见过的房间。一旦回到以前的某个房间，接下来的道路就会完全重复。因为每个房间的出口始终相同。

图33-4：有限状态序列的典型结构

查看 SVG 配图原件

33-008-c2c8130d5b7d.svg · 点击查看大图

抽象示意：有限状态的确定性生成器，最终必然进入某个循环。示意图中的状态编号不对应具体中平方法数值。

这揭示了一个更普遍的事实：任何内部状态数量有限、且不接受新输入的确定性伪随机数生成器，最终都会进入循环。真正的问题不是“它会不会循环”，而是：循环有多长？在进入循环之前，生成的数字是否具有足够好的统计性质？而中平方法的问题，在于它很容易过早进入短循环或者不动点。冯·诺依曼并非完全没有注意到这些缺陷。在1951年的讨论中，他就明确提到过生成序列末尾不断出现零的危险，以及潜在的短循环问题。因此，把中平方法描述成“冯·诺依曼一直认为完美，后来才被别人揭穿”的故事，并不符合历史。更准确的说法是：早期研究者已经认识到这些方法的缺陷，但在有限计算资源和当时的应用需求下，仍然积极探索如何设计并检验可用的数字序列。^[MCNP网站]这是一场研究尚不成熟的探索，而不是一次简单的失败。

第四幕：莱默的接力——让随机数字拥有更长的生命

美国数学家德里克·亨利·莱默（Derrick Henry Lehmer，1905—1991）。照片摄于其晚年，并非1949年的研究现场。到了1940年代末，生成随机数已经逐渐成为独立的计算问题。研究者发现，一个方法不仅要足够快，还需要能够控制周期长度。如果我们能够事先知道某个生成器的周期，那么至少可以避免在未知情况下突然掉入极短循环。这时，一位长期研究数论的数学家走进了故事。他叫德里克·亨利·莱默。

一个来自数论的办法

莱默对计算数论有深入研究，也对数学计算设备的实际能力十分了解。1949年9月，在哈佛大学举办的第二届大型数字计算设备研讨会上，他介绍了一种可以利用模运算产生数字序列的方法。相关论文《Mathematical Methods in Large-Scale Computing Units》于1951年收入会议论文集。这一方法的重要特点，是能够使用数论知识分析生成序列的周期。莱默早期提出的典型形式，是乘法同余生成器：

\boxed{x_{n+1}=ax_n\bmod m}

其中：

$x_n$ ：当前状态；
$a$ ：固定乘数；
$m$ ：模数；
$x_{n+1}$ ：下一个状态。

例如，当：

a=3,\quad m=17,\quad x_0=1

我们不断执行乘法与取余运算，便得到一个确定的数字序列。选择合适的乘数与模数，可以使序列拥有比较长、并且能够从数学上分析的周期。这比只依靠平方与截取中间数字，更容易进行系统设计。^{[informs-sim.org][303]}

从乘法同余到更一般的线性同余

后来，这一类方法形成了人们熟悉的线性同余生成器，简称 LCG（Linear Congruential Generator）。常见的广义形式为：

\boxed{x_{n+1}=(ax_n+c)\bmod m}

与前面的乘法形式相比，这里增加了一个常数

c

。它被称为增量。当

c=0

时，便回到乘法同余形式。我们用一个极其简单的教学例子：

x_{n+1}=(5x_n+1)\bmod16

设初始状态为：

x_0=3

那么：

x_1=(5\times3+1)\bmod16=0

下一步：

x_2=(5\times0+1)\bmod16=1

继续：

x_3=(5\times1+1)\bmod16=6

于是得到：

3\rightarrow0\rightarrow1\rightarrow6\rightarrow15\rightarrow12\rightarrow13\rightarrow2\rightarrow\cdots

这个例子有一个重要特点。它最终会遍历模16下的全部16个状态，然后回到3。也就是说，它的周期长度达到16。在这个有限状态空间内，它拥有完整周期。但我们马上需要小心。完整周期并不意味着真正随机，也不意味着统计质量一定优秀。例如，在这个例子中，由于乘数5是奇数，增量1也是奇数，输出数字的奇偶性会每一步交替变化。读者很容易发现：奇数。偶数。奇数。偶数。如此循环。尽管它能够遍历全部16个状态，却仍然包含非常明显的可预测规律。这说明，生成器的质量至少涉及两个不同的问题：它能产生多少不同状态？这些状态以怎样的顺序出现？第一个问题是周期。第二个问题是统计结构。而两者并不等价。

数学家发现，随机数字竟然排列在平面上

1968年，数学家乔治·马萨利亚（George Marsaglia）发表了一篇有趣的论文。题目叫：Random Numbers Fall Mainly in the Planes《随机数主要落在一些平面上》。他揭示了线性同余生成器隐藏的一个重要几何性质。如果将连续生成的数字组合成二维、三维或更高维的点，那么这些点并不是毫无结构地填满空间。它们会落在有限数量的平行直线、平面或更高维超平面上。

线性同余生成器的格点结构可视化参考。连续的伪随机数在高维空间里可能呈现规则排列，而不是像理想的独立随机样本那样散布。这项发现令人震惊。一组数字，即使单独看起来很杂乱，放到更高维的空间中，也可能暴露出明显的规律。这种规律可能影响数值积分、蒙特卡洛模拟和其他科学计算。马萨利亚的研究进一步提醒计算机科学家：不能因为某种生成器的数字看起来很混乱，就认为它一定可靠。^{[PMC][PubMed]}从中平方法到线性同余方法，研究人员不仅学会了如何产生数字，还逐渐学会了分析数字之间隐藏的结构。但这场探索并不只有算术方法。在同一个年代，还有人选择了完全不同的道路。如果计算机无法凭空产生真正的偶然性，那么我们能不能直接从物理世界里获取它？

第五幕：一本写满数字的书——兰德公司的百万随机数

兰德公司1955年出版的《一百万个随机数字与十万个正态偏差》。这部著作的大部分内容是一张张密密麻麻的随机数字表。^[RAND]1955年，美国出版了一本非常特殊的书。它没有小说情节。没有诗歌。也没有通常意义上的章节正文。它最重要的内容，是大量的数字。书名叫作：A Million Random Digits with 100,000 Normal Deviates《一百万个随机数字与十万个正态偏差》。出版这本书的，是兰德公司（RAND Corporation）。为什么有人要花费大量精力，出版一本几乎写满数字的书？在今天，这听起来似乎是一项荒唐的工程。任何普通程序员都可以很快生成大量伪随机数。但是在二十世纪四五十年代，情况完全不同。研究人员需要大量随机样本，进行统计分析、科学实验和蒙特卡洛模拟。而现成的、经过检验的大型随机数字表，并不像今天这样容易获得。于是，兰德公司决定自己制造一份。

一台电子轮盘

他们没有简单地使用中平方法。而是设计了一种专门产生随机数字的电子装置。这套设备常被称为电子轮盘（Electronic Roulette Wheel）。根据兰德公司官方出版物中的介绍，装置利用变化的电脉冲信号，通过计数器和数字转换电路，产生用于随机数表的原始数据。这个过程可以简单理解成：从物理过程获得变化信号。通过电子电路对信号进行采样和计数。再把结果转换为数字，记录在穿孔卡片上。不过，实际的技术细节比这个概括复杂得多。兰德公司的设备利用平均每秒约十万个脉冲的信号源，通过门控和计数电路产生候选数值，并进行了筛选和转换。乍看之下，这似乎比算术生成器更加可靠。因为这些数字至少不完全来自一个固定的数字递推公式。但工程师很快遇到了麻烦。

物理随机，也会有偏差

原始设备产生的数字，经过统计检验之后，竟然出现了显著的偏差。某些数字或数字组合的频率，没有达到预期的统计表现。工程师进行了修改和调整。在1947年5月和6月，他们制成了一份拥有一百万个数字的基础数据表。然而，继续检测之后，研究人员又发现了较小、但统计上仍然显著的偏差。更令人意外的是，设备即使经过调整，长时间运行之后，统计性质也可能发生变化。这说明：从物理过程获取随机性，并不能自动保证最终数字毫无偏差。随机源可能存在偏倚。电子设备可能产生相关性。测量与转换过程也可能引入新的规律。因此，研究人员还需要进一步处理和检验数字。兰德公司的团队最终采用了一项重新随机化处理：把相邻卡片对应位置上的数字按模10进行相加，以改善数据表的统计分布。这套经过处理的数字表，后来被正式出版。值得注意的是，原始数据产生于1947年，而著作的正式出版时间是1955年。不能把两个日期混为一谈。这些过程都在兰德公司保存的官方资料中有详细记录。^[RAND][RAND]

为什么不直接把电子轮盘接到计算机上？

既然电子装置能够产生随机数字，为什么还需要研究伪随机数算法？这个问题，冯·诺依曼在1951年的讨论里已经提出。其中一个关键原因，是重复计算。假设某位研究人员运行了一次模拟。结果很奇怪。他怀疑某一步程序存在错误。于是决定重新运行。如果第二次使用了完全不同的随机数字，那么即使程序没有修改，结果也可能发生变化。这样一来，他很难判断：究竟是程序出现问题？还是两次抽样本来就不同？反过来，如果随机序列能够被完整重现，那么研究人员便可以在完全相同的随机条件下，逐步检查程序。只需要保存生成器使用的种子及其他必要状态，就能够重复整个计算过程。冯·诺依曼明确注意到了这种需求：对于需要调试和核查的数值计算而言，每次直接使用新产生的物理随机数字，会增加重复实验的困难。^[MCNP网站]于是，伪随机数原本看起来像一种缺陷的性质，反而变成了它的重要优势。同样的种子，能够重新得到同样的序列。这意味着，一个看似随机的实验过程，可以被精确复现。科学需要探索不确定性。同时，科学也需要可重复性。而伪随机数恰好能够在这两种需求之间，建立一种独特的联系。

第六幕：看起来混乱，并不代表真正随机

骰子是研究随机性的经典对象。但在理想数学模型中被视为随机的结果，也可以从物理动力学角度研究其运动过程。随机性与可预测性并不是完全相同的概念。现在，我们已经认识了两种不同的随机数来源。一种来自确定性的数学算法。另一种来自具有不确定性的物理过程。但怎样判断生成的数字是否合格？我们不妨从最简单的游戏开始。

一枚总是正面朝上的硬币

假设有一枚硬币。你将它投掷1000次。结果全部是正面。从数学上说，对于一枚理想且独立投掷的公平硬币，这种情况并非绝对不可能。但是，它发生的概率极低：

P=\left(\frac12\right)^{1000}

我们当然有理由怀疑：这枚硬币是否存在偏差？投掷方法是否具有某种固定规律？甚至，记录数据的人是否犯了错误？这种检查，是随机性统计检验最直观的形式。

检验一：频率是否均衡？

如果我们希望产生0到9之间均匀分布的数字，那么每个数字在长期统计中的出现比例，应当接近10%。假设产生10000个数字。理想情况下，每个数字的期望出现次数是1000次。但要注意：这不意味着每个数字都必须恰好出现1000次。真正的随机序列也会存在波动。反过来，刻意制造一串每个数字都恰好出现1000次的序列，也不能证明它具有独立随机性。例如：

0123456789\,0123456789\,0123456789\ldots

这串数字的频率非常均匀。但是它的规律，几乎一眼就能看出来。因此，只检查频率远远不够。

检验二：数字之间是否存在关系？

研究人员还会关注数字之间的相关性。例如，如果某个生成器只会按顺序产生：

1,2,3,4,5,6,7,8,9,0

并不断循环，那么每个数字的出现频率虽然相同，但下一个数字完全可以预测。为了识别这类问题，可以检查连续数字组合的分布、相关系数、游程长度，以及更高维的统计结构。马萨利亚在1968年的研究中所揭示的格点现象，正是这种分析思路的重要成果。

检验三：数字是否容易预测？

还有一个比频率和相关性更加严格的问题。假设一个攻击者观察到了生成器输出的前面一部分数字。他是否能够根据这些数字，推算出下一次的输出？这个问题，对密码学尤其重要。我们考虑两个生成器。生成器A产生的数字，在频率和相关性测试中看起来都不错。但攻击者只需要观察几个输出，就能够还原其内部状态。生成器B不仅具有良好的统计性质，而且在适当的安全假设与实现条件下，攻击者即使掌握算法、观察输出，也难以预测未来的数字。对于一般的模拟任务，生成器A在某些条件下可能已经足够。但是，如果这些数字被用于生成加密密钥、登录令牌或安全验证码，生成器A就可能带来严重风险。这就是普通伪随机数生成器和密码学安全伪随机数生成器（CSPRNG）之间的重要差别。美国国家标准与技术研究院（NIST）明确指出：统计测试可以帮助发现随机数生成器的问题，但不能单凭通过统计测试，就证明它适用于密码学。^[CSRC]

三种随机数的区别

类型	主要特征	典型用途
物理随机源	利用物理过程获取熵，需要采集和质量处理	安全系统的熵来源
普通伪随机数	由算法和种子确定，便于重复实验	游戏、模拟、数值计算
密码学安全伪随机数	由安全设计的算法生成，强调计算上的不可预测性	密钥、令牌、安全通信

实际上，现代安全系统经常将这几种技术组合使用。从物理或其他经过评估的熵源获取初始随机性。再经过适当处理，用于初始化密码学安全的确定性随机比特生成器。这样既可以获得高效的数字生成能力，又能够满足安全需求。NIST SP 800-90 系列标准正是围绕确定性生成器、熵源以及它们的组合展开的。^[CSRC][CSRC]随机数研究因此从早期的“怎样制造数字”，发展成了一个非常完整的技术领域。它需要概率论。需要数论。需要统计学。需要密码学。也需要电子工程与计算机系统知识。而这一切，最初都与那个简单的问题有关：计算机怎样掷骰子？

第七幕：亲手制造一台会陷入循环的随机数机器

早期计算机常通过穿孔卡片输入程序和数据。今天我们可以通过几行程序重现当年需要专门计算设备才能研究的随机数实验。现在，我们已经知道中平方法存在危险。但只阅读数学公式，不如亲手观察一次。下面，我们建立一台简单的伪随机数生成器。你可以自由设置初始种子，并在两种算法之间切换。第一种是四位中平方法。第二种是为了教学设计的线性同余方法：

x_{n+1}=(21x_n+1)\bmod10000

这里特意选择了较小的状态空间，方便观察。它并不是某个现代工业级随机数库的参数配置。

实验一：随机数的命运由种子决定

图33-5：伪随机数实验室所有计算都在当前界面执行。修改种子或算法，观察序列变化。

选择生成算法

初始种子（0—9999）

生成次数24

不同输出值

4

本次24个输出中

首次发现的循环长度

4

第4步首次重访状态

当前生成序列

2100

4100

8100

6100

2100

4100

8100

6100

2100

4100

8100

6100

2100

4100

8100

6100

2100

4100

8100

6100

2100

4100

8100

6100

展示前24个输出。即使出现了很多不同的数字，也不意味着序列已经通过随机性检验。

计算细节

步骤	平方（8位）	输出
1	37210000	2100
2	04410000	4100
3	16810000	8100
4	65610000	6100
5	37210000	2100
6	04410000	4100
7	16810000	8100
8	65610000	6100
9	37210000	2100
10	04410000	4100
11	16810000	8100
12	65610000	6100

输出的分布将0—9999分成10个等宽区间，统计本次各区间的出现次数。少量数据不能用于确定随机数生成器的最终质量。

观察结论在生成过程中发现重复状态。首次重复形成的循环长度为4。由于算法完全确定，一旦进入这个循环，此后就会重复。

你可以先完成三次实验。先选择中平方法，并使用6100作为种子。观察序列是否陷入长度为4的循环。再改成2500。你会发现它从一开始就停留在同一个状态。最后，换成线性同余方法。在相同种子下，观察输出序列是否改变，短时间内是否还能发现重复。这些实验不会告诉你哪一个生成器适合真实密码系统，但它们能够让你真正理解随机数生成器的内部结构。

实验二：自己编写中平方法

我们用 Python 实现完整程序。


def middle_square(seed: int, count: int = 20):
    if not 0 <= seed <= 9999:
        raise ValueError("种子必须在0到9999之间")

    x = seed
    result = []

    for _ in range(count):
        square = str(x * x).zfill(8)
        x = int(square[2:6])
        result.append(x)

    return result


for seed in [1000, 2500, 6100, 1234]:
    numbers = middle_square(seed, 12)

    print("种子:", seed)
    print(numbers)
    print()

你会发现：相同种子总是产生相同结果。这是伪随机数可复现性的直接体现。接下来，试着不再只生成12个数字，而是生成1000个。统计其中有多少不同的值。再尝试自动检测第一次重复出现的位置，计算循环长度。如果你能够完成这些任务，实际上已经开始研究一个随机数生成器的内部状态转移结构。

实验三：让两次模拟使用完全相同的随机数

现代 Python 标准库中的 random 模块，提供了比中平方法成熟得多的普通伪随机数生成器。下面用它模拟投掷骰子：


import random


def roll_dice(seed: int):
    rng = random.Random(seed)

    return [rng.randint(1, 6) for _ in range(10)]


first = roll_dice(2026)
second = roll_dice(2026)
third = roll_dice(2027)

print("实验一:", first)
print("实验二:", second)
print("实验三:", third)

print("前两次完全相同:", first == second)
print("第一与第三次相同:", first == third)

前两次一定得到完全相同的结果。第三次更换了种子，通常会生成不同的序列；并不是数学上保证两个不同种子绝不会得到相同的有限输出片段。这就是早期科学家特别重视伪随机数的一项原因。他们希望能够模拟不确定性的同时，又可以重复实验、查找问题、比较计算结果。今天，在机器学习训练、计算物理、自动化测试以及游戏世界生成中，这个需求仍然广泛存在。

第八幕：从科学实验到现代数字安全

现代计算机的安全系统需要可靠的随机性。安全密钥的生成通常依赖经过评估的熵来源与密码学安全随机数生成机制。现在，故事跨越了七十多年。计算机不再占据整个房间。我们每个人手中的设备，都拥有远超早期电子计算机的计算能力。但冯·诺依曼时代的问题并没有消失。它只是变得更加复杂。

游戏中的随机世界

想象一个程序生成的迷宫。游戏希望每次进入时，地图都不一样。房间的位置不同。宝箱出现的地点不同。怪物的行动也有所变化。这些内容可以使用伪随机数算法生成。如果保存同一个种子，就可以重新生成相同的地图结构。这也是很多程序化世界生成技术的重要基础。当然，完整的可复现性还要求生成算法、参数和调用顺序等条件保持一致。随机种子不是唯一需要保存的信息。

科学计算中的共同起点

假设两位研究人员要比较两种优化算法。如果两种方法面对的随机测试条件完全不同，就很难判断性能差异究竟来自算法，还是来自测试环境。因此，研究人员经常使用受控的随机种子。让不同算法在可比的随机条件下运行。再通过多组不同的种子，检验结果是否具有稳定性。这样可以同时利用伪随机数的两种特点：重复某次实验。探索许多不同的随机情形。在严谨的研究中，仅使用一组固定种子通常并不足以证明算法的综合性能。

密码学中的随机性

但对于密码系统，问题又发生了变化。如果一个攻击者能够猜出生成器使用的种子，或者通过输出推测未来的随机数字，那么系统可能受到严重威胁。因此，不能把中平方法、教学用线性同余方法，或者普通的 random 模块，直接当成安全密钥生成器。在 Python 中，如果需要生成安全令牌，应使用专门的密码学随机接口，例如：


import secrets

# 生成32字节的密码学随机令牌
token = secrets.token_hex(32)

print(token)

secrets 使用适合安全用途的系统随机源，而不是依靠调用者设置一个普通的固定种子来生成可复现的序列。不过，现代密码学安全随机数生成机制也并不是神奇的例外。许多安全生成器内部同样使用确定性算法。它们的安全性来自经过分析的密码学结构、足够的初始熵、合理的状态管理，以及正确的实现。从这个角度看，冯·诺依曼时代的思想并没有被抛弃。它被不断改进、完善，并融入了更复杂的安全系统。

尾声：数学能否制造偶然？

让我们回到1940年代末。那时候，科学家正第一次认真思考：一台高速电子计算机，究竟应该怎样处理随机性？他们拥有越来越强大的计算机器。但机器只能执行确定性指令。于是，他们尝试寻找一种折中的道路。不要求每一个数字都来自新的物理偶然事件。而是让算法生成一串具有适当统计性质的数字。冯·诺依曼的中平方法，提供了一个简单而重要的早期探索案例。它清楚地展示了这种思路的可能性。也暴露了这种思路的危险。一个数字可以跌入零的陷阱。可以停留在不动点。也可以被困在长度极短的循环中。后来，莱默等数学家将数论方法引入随机数生成器设计。研究人员开始能够分析周期、选择参数、研究数字之间的相关性。而在另一条道路上，兰德公司的工程师尝试从物理过程获取随机数字，却同样发现随机源可能存在偏差，需要加工与检验。人类最终认识到：随机性并不是一个简单的开关。它不是把一个程序标记成“随机”，就自然出现的性质。它需要明确的数学定义。需要统计分析。有时需要物理熵源。如果应用于密码学，还需要更加严格的安全要求。但在这一切之中，有一个看似矛盾的结论格外重要。计算机的确定性，并不总是它的缺点。恰恰因为计算机按照确定规则执行，我们才能在模拟世界中创造可以重复的复杂实验。我们可以让一个程序生成一百万次看似随机的事件。然后，保存种子。重新开始。让整个数字世界，再经历一次完全相同的演化。这不是传统意义上的真正偶然。但它是一种非常有用、也非常强大的计算能力。在欧几里得算法中，我们看到了确定性规则怎样保证答案正确。在快速傅里叶变换中，我们看到了确定性规则怎样大幅减少计算量。到了伪随机数生成器，我们又发现：确定性规则，竟然可以帮助人类研究不确定的世界。从秩序中模拟偶然。再通过偶然探索规律。这正是计算科学发展史上一次深刻的思想转变。计算机不一定需要真正地掷出骰子，才能帮助人类理解一个充满偶然性的世界。

历史档案：本章主要参考资料

本章涉及的主要历史文献与研究资料如下，均可作为后续独立出版时的事实核查依据。

John von Neumann：Various Techniques Used in Connection with Random Digits。1951年发表的会议讨论记录，文中涉及中平方法、物理随机源、可复现性和统计检验。
ENIAC Goes to Monte Carlo。Thomas Haigh 等人的计算机史研究，详细讨论1947年 ENIAC 蒙特卡洛计算的计划与参与者。
History of Uniform Random Number Generation。梳理随机数生成技术的发展，包括莱默1949年的工作。
RAND：A Million Random Digits with 100,000 Normal Deviates。兰德公司的官方出版物，记录电子轮盘、1947年原始数字表的产生、统计偏差和1955年出版情况。
George Marsaglia：Random Numbers Fall Mainly in the Planes。1968年发表于《美国国家科学院院刊》的研究论文。
NIST：Random Bit Generation。现代随机比特生成器、熵源和密码学应用的标准资料。

本章开篇对早期实验室气氛和研究困境的描述属于历史背景下的文学性重构，不对应某次有完整记录的具体对话。ENIAC 的蒙特卡洛研究、中平方法的数学机制、莱默的会议工作、兰德公司的随机数表和马萨利亚的论文则均有相关史料支持。所有四位数字示例、循环结构图、交互实验和 Python 代码均为现代教学设计，而不是历史人物的原始计算记录。

下一章预告 · 第34章

《用一百万次偶然寻找答案：蒙特卡洛方法》

1940年代，一位正在康复中的数学家，回忆起一项看似普通的纸牌游戏。他开始思考：如果某个问题的全部可能性过于庞大，无法逐一求解，能不能通过一次又一次随机试验，慢慢逼近真正的答案？这种思想后来成为蒙特卡洛方法的重要历史线索。下一章，我们将来到洛斯阿拉莫斯实验室，认识乌拉姆、冯·诺依曼与梅特罗波利斯，追踪蒙特卡洛方法的真实发展过程。从一副纸牌开始，到粒子输运，再到使用随机投点估算圆周率。我们将看到，人类是怎样把无法穷尽的巨大问题，转化为可以不断改进的统计估计。

——《算法的故事》第二季 · 第33章完