素数

先看一个麻烦

给你一个数：91。它是素数吗？

你会开始试除：能被 2 整除吗？不能（是奇数）。3 呢？9+1=10 不是 3 的倍数，不能。5 呢？末位不是 0 或 5，不能。7 呢——91 ÷ 7 = 13。整除。所以 91 = 7 × 13，是合数。

现在换一个数：2^82589933 − 1。同样的问题。

试除法在这里彻底失效。这个数有两千多万位，要试除的候选比宇宙里的原子还多。

朴素方法，以及它为什么不够

试除法的正确写法是：只需试到 √n 就够了。因为如果 n = a × b 且 a ≤ b，那么 a 一定不超过 √n。判断 91 只需试到 9，四个候选，很快。

但”只需 √n”听起来省，实际上仍然是灾难。比特币用的私钥是 256 位的数，√n 大约是 2^128 ≈ 3×10^38。哪怕每秒试一万亿次，也要跑上 10^19 年。

问题的关键在于：√n 是 n 的平方根，但相对于”输入长度”却是指数级的。一个 n 位的数，√n 需要约 2^(n/2) 步。输入每多一位，工作量翻 1.4 倍。

这正是多项式时间这个概念要刻画的差别：我们要的是随位数增长而缓慢增长的算法，不是随数值增长的算法。

机制：素数是乘法的原子

素数的定义是：大于 1、且只能被 1 和自身整除的整数。前几个是 2, 3, 5, 7, 11, 13。

它们重要不是因为定义特别，而是因为一条定理（算术基本定理）：每个大于 1 的整数都能唯一地分解成素数的乘积。

12 = 2 × 2 × 3
91 = 7 × 13
100 = 2 × 2 × 5 × 5

唯一——顺序不计，分解方式只有一种。所以素数是整数在乘法下的构造单元，就像原子对分子。

素数有无穷多个，欧几里得两千多年前就证明了，证法只有三行：假设素数有限，把它们全部乘起来再加 1，得到的数不被任何已知素数整除，矛盾。

回访：为什么密码学要这个

现代公钥密码建立在一个不对称上：

• 把两个大素数乘起来：极快
• 把乘积拆回两个素数：极慢（没有已知的多项式时间算法）

RSA 就住在这个缝隙里。所以密码学需要大量的大素数，也就需要一个快速的素性判定方法——注意，是判定”是不是素数”，不是”分解成什么”。这两个问题的难度完全不同：2004 年 AKS 证明了判定属于 P，而分解至今没人知道属不属于 P。

这个区分是读《PRIMES is in P》时最容易搞混的地方，也是”AKS 破解了 RSA”这类说法错在哪里。

边界与常见误解

**1 不是素数。**这不是约定俗成的随意规定：如果把 1 算进来，唯一分解就失效了（12 = 2×2×3 = 1×2×2×3 = 1×1×2×2×3……）。

**2 是素数。**它是唯一的偶素数。“素数都是奇数”是错的。

**判定和分解不是同一件事。**你可以确知一个数是合数，却完全不知道它的因子是什么——费马检验就是这样：它告诉你”这数不是素数”，但一个因子也给不出来。