确定性算法

先看一个麻烦

给你一个 400 位的数，问它是不是素数。

有个办法快得惊人：随机挑几十个数当”证人”，让每个证人做一次小测验。如果某个证人指认这个数是合数，那它铁定是合数。如果所有证人都说”像素数”，你就宣布它是素数。

这个办法在实践中好用到什么程度？你现在访问的每个 HTTPS 网站，背后的密钥都是这么生成的。

但它有个让人不舒服的地方：它可能出错。所有证人都被骗过的概率不是零，只是小到可以忽略——大约 4⁻ᵏ，k 是证人个数。挑 50 个证人，出错概率比你的硬盘自发翻转一个比特还小。

工程上这没问题。数学上这是个未了的问题：我们从没证明过素数判定可以不靠运气。

朴素办法：把随机数换成固定的几个

既然随机挑证人有效，那干脆固定用前 k 个素数当证人，不就”确定”了吗？

这条路真的有人走。问题在于，没人能证明前多少个素数就够。已知的结论都带前提：如果广义黎曼猜想成立，那么检查前 O((log n)²) 个证人就足够。

“如果某个未解决的猜想成立”——这不叫证明，这叫欠条。

机制：确定性意味着什么

一个算法是确定性的，指的是它的执行路径完全由输入决定。没有随机数发生器，没有”随便挑一个”，同一个输入跑一万遍，经过的每一步都一样，输出也一样。

对照着看就清楚了：

• 确定性：给定 n，步骤固定，答案固定，永远正确。
• 随机化（Monte Carlo）：允许小概率给出错误答案，换来速度。
• 随机化（Las Vegas）：答案永远正确，但运行时间是随机的。

素数判定的处境曾经是：有多项式时间的随机化算法（Miller–Rabin，1976/1980），有确定性但慢的算法（试除法，指数时间），中间那格——确定性 + 多项式时间——空着。

2002 年，Agrawal、Kayal 和 Saxena 把它填上了。他们论文的第一句话就是在宣布这件事：

We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite.

我们给出一个无条件的、确定性的、多项式时间算法，判定输入的数是素数还是合数。

三个形容词各自都在还一笔债。unconditional：不依赖黎曼猜想之类的未证前提。deterministic：不掷骰子。polynomial-time：不是指数级的慢。

回访：为什么这件事值得写进《数学年刊》

如果随机化算法已经足够快、足够可靠，为什么还要一个更慢的确定性算法？AKS 的实际运行时间比 Miller–Rabin 慢得多，至今没有密码库用它。

因为问的不是同一个问题。

工程问的是”能不能算出来”。数学问的是”随机性是不是必需的”。素数判定曾是”看起来必须靠随机才能快”的头号例子，AKS 把它移出了这份名单——这是关于计算本身的一个结论，不是关于素数的。

这也是复杂性理论里一个更大问题的局部战果：BPP（随机化多项式时间）到底是不是等于 P（确定性多项式时间）？多数人猜相等，也就是说随机性能加速的一切最终都能被去随机化。AKS 是这个方向上少数几个真正拿下的实例。

边界

确定性不等于”没有不确定”。一个确定性算法在浮点运算下仍可能因为硬件差异给出不同结果，在并发下仍可能因为调度顺序变化——这些是实现层的不确定，不是算法层的。

反过来，“确定性”也不保证快。试除法是确定性的，但判定一个 400 位数要跑到宇宙终结。确定性和多项式时间是两个独立的要求，AKS 的分量在于同时满足。