随机算法

一个算法，通常被认为是确定性的：给定相同的输入，它每次都执行相同的步骤，给出相同的输出。而随机算法（Randomized Algorithm）在执行过程中会抛硬币——使用随机数来做决策，使得同一输入在不同运行中可能走不同的路径。

这听起来像是在引入不可靠性。实际上，在很多问题上，随机化是到达正确答案最快、甚至唯一已知实用的路径。

随机算法的故事在 1970 年代后期成形：1977 年，罗伯特·索洛瓦（Robert Solovay）与沃尔克·施特拉森（Volker Strassen）提出了第一个实用的概率素数检测算法；1980 年，迈克尔·拉宾（Michael Rabin）把加里·米勒（Gary Miller）1976 年那个依赖未证黎曼猜想的确定性测试，改造成了无需任何未证假设的概率版本（即米勒-拉宾测试）。素数检测在密码学中极为关键，而这些随机化的解法远比当时已知的任何确定性方法快。

破除误解：随机不等于不可靠#

"随机算法可能给出错误答案"——这句话是真的，但会误导人，因为它省略了最重要的部分：错误概率是精确可控的，通常极小。

以素数测试为例：拉宾-米勒素数测试（Miller-Rabin Primality Test）是蒙特卡洛算法，对合数可能给出错误的"是素数"判断。拉宾 1980 年的经典分析证明：对任意奇合数，至多四分之一的基底是“强谎言者”。因此独立重复 $k$ 次，把合数误判为素数的概率至多 $4^{-k}$。取 $k = 40$，错误概率小于 $4^{-40} \approx 10^{-24}$——比你的计算机因宇宙射线发生硬件错误的概率还低几个数量级。在实际工程中，这种算法的可靠性是可以接受的。

随机算法的"不可靠"，是被数学精确控制的、可以被调整到任意小的不可靠性——这与日常语言中"不可靠"的含义完全不同。

两类随机算法：拉斯维加斯与蒙特卡洛#

这两类算法的命名来自两个赌城，因为它们都涉及随机性和风险，但风险的方向不同：

拉斯维加斯算法（Las Vegas Algorithm）： - 总是给出正确答案（绝不撒谎） - 运行时间是随机的（不保证快，但期望是快的） - 例子：随机快速排序（Randomized Quicksort）

拉斯维加斯这个名字由拉斯洛·巴拜（László Babai）在 1979 年提出——Las Vegas 赌场保证给你钱（输的是你的时间），但你不知道会赢多少次才离开。

蒙特卡洛算法（Monte Carlo Algorithm）： - 总是在有限时间内结束（快） - 结果可能有错误（以可控概率） - 例子：米勒-拉宾素数测试、随机近似算法

蒙特卡洛的命名来自二战期间美国物理学家乌拉姆（Stanislaw Ulam）和梅特罗波利斯（Nicholas Metropolis）用于核武器模拟的统计方法，1949 年正式命名，是随机计算方法最早的主要应用。

两类算法都靠同一件数学事实变可靠：独立重复会把坏事件的概率指数压下去。这就是误差放大。以单侧错误的蒙特卡洛为例。一次运行把合数说成素数的概率不超过 $1/4$。独立再跑 4 次，五次全骗过你的概率不超过 $4^{-5} = 1/1024$，大约千分之一。再跑到 10 次，$4^{-10} = 1/1\,048\,576$，大约百万分之一。代价随次数线性增加，错误率按 $4^{-k}$ 下降。双侧错误的 BPP 算法用多数票，切尔诺夫界（Chernoff, 1952）保证：要把错误率从 $1/3$ 压到 $\delta$，只需要 $\Theta(\log(1/\delta))$ 次独立重复。想要 $10^{-6}$ 的错误，大约一百次多数票就够，不需要成千上万次。

拉斯维加斯的放大方向相反：它从不撒谎，只可能超时。假设某次运行在预算 $T$ 内结束的概率至少 $1/2$，超时就中止重来。独立重启 8 次仍未完成的概率是 $2^{-8} = 1/256$，大约 0.4%。期望重启次数是 2。你买到的是“几乎总在 $O(T)$ 内给出正确答案”，付出的是一个随机的等待。

核心案例一：米勒-拉宾素数测试#

问题：给定大整数 $n$，判断它是否是素数。

为什么重要：RSA 加密和许多其他密码协议需要生成大素数（如 1024 位或 2048 位的素数）。找到大素数的方法是：随机生成一个大奇数，测试它是否是素数，重复直到找到一个素数。因此，素数测试的效率直接影响密码系统的密钥生成速度。

这条算法有一段被经常说错的家谱。米勒 1976 年在《计算机与系统科学杂志》上给出的测试是确定性的：在广义黎曼猜想（GRH / 扩展黎曼假设）成立的前提下，检查到大约 $O((\log n)^2)$ 个基底就足够判定素性。猜想尚未被证明，所以这个确定性版本不能单独走进密码库。拉宾 1980 年去掉了未证假设，改成随机抽取证人，并证明至多四分之一的基底是强谎言者。于是错误概率有了不依赖任何猜想的上界 $4^{-k}$。

费马小定理基础：若 $n$ 是素数，则对任意 $a$（$\gcd(a, n) = 1$），有 $a^{n-1} \equiv 1 \pmod{n}$。如果这个等式不成立，$n$ 一定是合数。

但有些合数也满足这个等式（称为卡迈克尔数，Carmichael numbers），所以单用费马小定理不够。

米勒-拉宾测试：写 $n - 1 = 2^s \cdot d$（$d$ 为奇数），随机选取证人 $a$，计算序列 $a^d, a^{2d}, a^{4d}, \ldots, a^{2^s d} \pmod{n}$。如果 $n$ 是素数，这个序列要么从头开始就是 1，要么在某处第一次出现 $-1 \equiv n - 1$。若都不满足，$n$ 一定是合数；若满足，$n$ 大概率是素数（$a$ 揭露 $n$ 为合数的概率至少 3/4）。

重复 $k$ 次随机选取 $a$，错误概率降到 $4^{-k}$。$k=40$ 时这个最坏上界已经是 $2^{-80}$。生产密码库不会对所有位长使用同一个 $k$：NIST FIPS 186-4/186-5 按素数长度给出轮数表（更大的素数通常更少轮，因为随机合数更容易被揭穿），OpenSSL 的 libcrypto、GnuPG 的 libgcrypt 跟的是这类随位长变化的表，而不是固定的 20–40 轮。需要强调：这个 $4^{-k}$ 是最坏情况下合数蒙混过关的上界。对绝大多数合数，强谎言者远少于四分之一；但若对手可以特选伪素数，工程上仍应按最坏上界选 $k$。

2002 年，阿格拉瓦尔、卡亚尔和萨克塞纳宣布了 AKS 算法，并于 2004 年发表在《数学年刊》：这是第一个无条件的多项式时间确定性素数检测。它证明 PRIMES 属于 P，是理论里程碑。它没有满足广义黎曼猜想，也不依赖随机性。实践中它比米勒-拉宾慢，密码库仍主要使用米勒-拉宾。随机化在这里赢的不是“能不能判定”，而是“在可接受时间内把错误压到硬件故障以下”。

核心案例二：随机快速排序#

快速排序（Quicksort）的经典版本在最坏情况下是 $O(n^2)$（例如已排序数组加上固定选取第一个元素为枢轴）。

随机快速排序：每次随机选取枢轴，而不是选取固定位置的元素。

分析：对于任意输入，随机快速排序的期望运行时间是 $O(n \log n)$——不是在某些输入上 $O(n \log n)$，而是对所有输入，期望时间都是 $O(n \log n)$。最坏的 $O(n^2)$ 路径仍然存在，只是它现在取决于硬币，而不取决于输入的排列。对手无法通过精心构造坏输入来强迫算法进入 $O(n^2)$ 状态，因为他不知道算法会选择哪个随机枢轴。这是拉斯维加斯算法：答案永远正确，变慢的只是时间。

重复键会让朴素二分划变得尴尬。键大量相等时，二分划仍可能把几乎整个数组留在一侧。本特利与麦克罗伊 1993 年在重写 C 库 qsort 时，采用三路划分（fat partition）：小于、等于、大于枢轴的三段一次扫完，等于段不必再递归。这是对迪杰斯特拉“荷兰国旗”问题的工程解，不是新的随机性来源，却决定随机快排在真实数据上会不会退化。

这就是随机化的一个重要价值：防止对手利用确定性算法的可预测性。这在算法竞赛（防止刻意构造的极端数据）和密码学（防止攻击者利用确定性密钥生成的模式）中都有应用。

核心案例三：随机图算法与最小割#

最小割问题：给定一个图，找到最少的边，使得删去它们后图变成两个不相连的部分。

卡格尔算法（Karger's Algorithm，1993，SODA）是一个极为简单的随机算法：随机选一条边，把它连接的两个顶点合并成一个超级顶点（把多重边保留，删去自环）；重复直到只剩两个超级顶点；此时两超级顶点之间的边数就是一个割的大小。

单次运行得到最小割的概率至少为 $\frac{2}{n(n-1)}$（$n$ 为顶点数）。运行 $O(n^2 \log n)$ 次，可以以高概率找到最小割，总时间复杂度 $O(n^4 \log n)$。卡格尔与斯坦因 1996 年在《ACM 杂志》上的改进，利用“早期收缩更不容易毁掉最小割”这一观察，先收缩到约 $n/\sqrt{2}$ 个顶点再分叉递归，把高概率运行时间降到 $O(n^2 \log^3 n)$。这仍是蒙特卡洛：每次给出一个割，重复与分叉用来放大“恰好是最小割”的概率。

这个算法之所以有趣，是因为它极其简单——三行代码就能描述——但解决的是一个非平凡的组合优化问题。随机化使得原本复杂的算法设计变得异常简洁。

概率方法：存在性证明#

随机算法的一个更深层的应用，是保罗·厄多斯（Paul Erdős）发展的概率方法（Probabilistic Method）：通过证明"随机选取的对象以正概率满足某性质"，来证明满足该性质的对象存在，即使你无法给出具体构造。

例如，厄多斯 1959 年用概率方法证明：对任意正整数 $k$ 和 $g$，都存在色数大于 $k$、围长大于 $g$ 的图——也就是说，图可以既没有短环（因而最大团很小，连三角形都没有），又需要很多颜色。完全图 $K_n$ 的色数和团数都很大，那并不令人惊讶；真正要概率方法出力的，是色数大而团数小。他没有给出具体例子，只是证明随机图以正概率同时满足这两个条件。概率方法是组合数学、图论和理论计算机科学中最有力的证明工具之一。

存在性论证和算法不是同一件事。概率方法可以在你还不会构造对象时，先证明对象不是空集。卡格尔算法则多走了一步：它不但证明好的割以正概率出现，还把抽样本身写成可执行的程序。香农信道编码定理的原始证明停在第一层——"随机码"以正概率达到信道容量，却不给出具体码字。后来的编码理论，很多工作就是把这种存在性证明改造成多项式时间的构造。随机算法位于两者之间：有时它是被实现了的概率方法，有时它只是还没有被去随机化的存在性论证。

随机化与复杂性类#

随机算法定义了若干重要的计算复杂性类。类的清单与 P 对 BPP 的猜测，计算复杂性 一文已经写过，这里只补上算法侧真正用到的那一段。

BPP（Bounded-error Probabilistic Polynomial time）对应双侧错误的蒙特卡洛：多项式时间内结束，对或错的概率都不超过 $1/3$，再靠多数票放大。RP 是单侧错误：答案为“是”时至少以 $1/2$ 的概率正确，答案为“否”时绝不误报。米勒-拉宾测合数时属于 co-RP。ZPP 对应拉斯维加斯，$ZPP = RP \cap coRP$。

主要的开放问题仍然是：P = BPP 吗？ 目前大多数理论计算机科学家相信答案为是——随机性不增加多项式时间的计算能力。这条信念不是口号，它有一条条件式定理垫底。尼桑与维格德森 1994 年证明，足够硬的函数可以做成伪随机生成器，用来骗过多项式时间的测试。因帕利亚佐与维格德森 1997 年把硬度条件推到极限：如果指数时间类 $E = \mathrm{DTIME}(2^{O(n)})$ 里存在需要指数规模电路的语言，则 $P = BPP$。硬度换随机性。这与 平均情况复杂性与五个世界 里因帕利亚佐的五个世界是同一条河的两岸：一边问“随机实例是否仍然难”，一边问“难函数能否冒充硬币”。两者都还不是无条件定理。

代价：伪随机数的挑战#

随机算法的分析假设硬币是公平且独立的。实现里用的通常不是柏拉图式的真随机，而是分层的替代品。

最老的一层是冯·诺依曼 1951 年的去偏技巧：把有偏但独立的比特两两分组，01 输出 0，10 输出 1，00 与 11 丢弃。只要相继比特独立、偏置恒定，输出就是公平硬币。它不声称“计算机不能产生真随机”，它只是从一枚不公平的硬币里抽出公平性，并付出吞吐下降的代价。

现代机器上还有硬件真随机数发生器：热噪声、抖动、环形振荡器，以及操作系统汇入的熵池（键击、中断时刻、磁盘延迟）。它们提供的是物理不确定性和系统抖动，不是数学证明过的独立比特。密码学应用不能停在“看起来乱”。需要的是密码学安全的伪随机生成器（CSPRNG）：在多项式时间观察者面前，输出与真随机不可区分。理论上，这类生成器的存在与单向函数的存在等价，细节见 平均情况复杂性与五个世界。

质量不够时，后果不是“排序稍慢”，而是密钥直接可还原。2012 年，Heninger 等人在 USENIX Security 上的 "Mining Your Ps and Qs" 扫描全网公钥，发现数万台设备因生成密钥时熵不足而共享了相同的素因子——只要两把 RSA 公钥共用一个素数，对它们的模数求最大公约数就能瞬间分解、还原出私钥。随机算法把错误概率写成 $4^{-k}$；实现必须保证那枚硬币配得上这个式子。

跨域连接#

• 概率论：随机算法的"可能出错"与日常语义完全不同，因为错误概率是可控且可压的：独立重复若干次，错误率随次数指数下降。这把可靠性变成了一个预算问题——想要多可靠，就多跑几轮，代价是线性的而收益是指数的。五次证人把 $1/4$ 压到约千分之一，十次压到约百万分之一，是同一条切尔诺夫式算术的两个刻度。
• 核裂变：抽样估计的起点是一个物理问题：中子在材料中的输运方程维数太高，解析求解与网格求解都不可行，于是改用大量随机轨迹去估期望。这确立了一条通用套路：高维积分不算，改成采样，此后在金融、图形、统计中反复出现。蒙特卡洛这个名字从核模拟走进算法，不是修辞，是同一套期望估计。
• 组合数学：概率方法用"随机选取的对象以正概率具有某性质"来证明该对象存在，而不给出任何一个具体例子。存在性与构造性在这里被彻底分开——同一套论证也解释了为何存在逼近信道极限的好码，却不告诉你怎么造出来。卡格尔算法是少数把这套论证写成程序的例子：正概率不再只是存在性，而成了可重复的抽样。
• 临床试验：随机化在这里的用途不是提速，而是让分组独立于全部潜在结果，从而消灭混杂因素的构造能力。这与随机选枢轴防止对手构造最坏输入是同一个逻辑：随机性的价值在于让对手无法预测你的选择，无论对手是恶意输入还是系统性偏倚。
• 密码学基础：实现里用的是伪随机数，其质量直接决定安全。熵不足会让不同设备生成的密钥意外共享因子，此时无需攻破数学难题，求一次最大公约数即可——随机性从性能问题升格成了安全边界。米勒-拉宾在密码库里活到今天，靠的不是它比 AKS 更“正确”，而是它把错误压到硬件故障以下时仍然够快。

参考文献#

• Miller, G. L. Riemann's Hypothesis and Tests for Primality. Journal of Computer and System Sciences 13 (1976): 300–317.
• Rabin, M. O. Probabilistic Algorithm for Testing Primality. Journal of Number Theory 12(1) (1980): 128–138.
• Agrawal, M., Kayal, N. & Saxena, N. PRIMES is in P. Annals of Mathematics 160(2) (2004): 781–793. （2002 年宣布，2004 年正式发表）
• Karger, D. R. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. Proceedings of SODA (1993): 21–30.
• Karger, D. R. & Stein, C. A New Approach to the Minimum Cut Problem. Journal of the ACM 43(4) (1996): 601–640.
• Impagliazzo, R. & Wigderson, A. P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. Proceedings of STOC (1997): 220–229.
• Nisan, N. & Wigderson, A. Hardness vs Randomness. Journal of Computer and System Sciences 49(2) (1994): 149–167.
• von Neumann, J. Various Techniques Used in Connection with Random Digits. Applied Mathematics Series 12 (1951): 36–38.
• Bentley, J. L. & McIlroy, M. D. Engineering a Sort Function. Software: Practice and Experience 23(11) (1993): 1249–1265.
• Chernoff, H. A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations. Annals of Mathematical Statistics 23(4) (1952): 493–507.
• Heninger, N., Durumeric, Z., Wustrow, E. & Halderman, J. A. Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. USENIX Security (2012).
• Motwani, R. & Raghavan, P. Randomized Algorithms. Cambridge University Press (1995).
• Mitzenmacher, M. & Upfal, E. Probability and Computing. 2nd ed. Cambridge University Press (2017).
• Alon, N. & Spencer, J. H. The Probabilistic Method. 4th ed. Wiley (2016).
• Erdős, P. Graph Theory and Probability. Canadian Journal of Mathematics 11 (1959): 34–38.
• National Institute of Standards and Technology. Digital Signature Standard (DSS). FIPS 186-5, 2023.

延伸阅读#

• 复杂度类与 P 对 BPP 的全景，见 计算复杂性。
• 单向函数、伪随机生成器与因帕利亚佐的五个世界，见 平均情况复杂性与五个世界。
• 实现层的熵与密钥，见 密码学基础。