10.4. 寻找素数¶
我们如何判断一个数是否是素数？一种方法是素数筛：测试所有直到 \(\lfloor\sqrt{n}\rfloor\) 的素数。这最多需要 \(\lfloor\sqrt{n}\rfloor -1\) 次除法。
这个算法的成本与输入规模相比如何？一个问题实例是一个单独的值，而我们的模型说值 \(n\) 的规模是 \(\log n\)。因此，这是一个指数时间的算法！
注意，使用二进制表示时，很容易检查 2 整除 \(n\) 的次数。那检查 3 整除 \(n\) 的次数呢？这就不那么容易了。如果把 \(n\) 表示成三进制呢？那检查被 3 整除就容易了。
一般来说，是否存在多项式时间算法？我们不知道（而这一点对现代密码学至关重要，它依赖于"分解大数需要很多时间"这一"事实"）。但如果我们愿意接受一个概率算法呢？
以下是数论中的一些有用定理：
素数定理 ：小于 \(n\) 的素数个数为 （约） \(\frac{n}{\ln n}\)。
小于 \(n\) 的素数之间的平均距离是 \(\ln n\)。
素因子分布定理 ：对大的 \(n\)， 平均而言，\(n\) 有大约 \(\ln \ln n\) 个不同的素因子，标准差为 \(\sqrt{\ln \ln n}\)。注意这是相当小的。对 \(2^{32}\)，\(\log \log n = 5\)。
要证明一个数是合数，我们只需要一个因子。而且，给定一个（声称的）因子，很容易验证这一声称是否为真。要证明一个数是素数需要什么呢？证明某个数是素数的难度远大于证明某个数是合数！因为我们需要检查的远不止一个值。
为了判断 \(n\) 是否为素数，我们是否需要检查全部 \(\sqrt{n}\) 个候选因子？这取决于你希望多保险。（当然，我们实际上只需要检查小于 \(\sqrt{n}\) 的素数。）
下面是一些我们可能用来判断值 \(n\) 是否素数的潜在概率算法。
总是说 Prime(\(n\)) 是 FALSE。 这个简单算法"通常"有用。平均而言它只在 \(1/\log n\) 的情况下出错！
如果你不喜欢对真实素数值它总是出错的想法，那么 一个替代方案是，以概率 \(1/\ln n\) 说 Prime(\(n\)) 是 TRUE。虽然它对错参半，当然它并不比前一个算法好。
在 2 和 \(\sqrt{n}\) 之间挑一个数 \(m\)。 当且仅当 \(m\) 不整除 \(n\) 时说 \(n\) 是素数。这帮助不太大，因为它可能 没有 选中一个因子！
上述没有一个是真正严肃的、解决该问题的概率算法。然而，利用数论，有可能创建一个廉价的检验，它以概率方式判断一个数是否为合数（如果它确实是合数的话），正确率为 50%。使用这个检验，我们可以按照如下方式构建一个素性检验算法:
Prime(n) {
for(i=0; i<COMFORT; i++)
if !CHEAPTEST(n)
return FALSE;
return TRUE;
}
换句话说，我们可以反复尝试这个检验，直到我们的数字通过了足够多次，让我们放心地声称它是素数。当然，这对帮助你找到因子并无帮助！但这种方法有一个好处。我们使用大素数进行密码学。但是，所使用的数字其实并不需要是素数。它们只需要难以分解！而那些能持续通过廉价 50/50 检验的数往往难以分解。所以，即使使用了一个不是素数的数，它很可能仍会在预期的用途上成功。
