2. 寻找素数¶
我们如何判断一个数是否是素数？ 一种方法是素数筛： 测试所有直到 \(\lfloor\sqrt{n}\rfloor\) 的素数。 这最多需要 \(\lfloor\sqrt{n}\rfloor -1\) 次除法。
这个算法的代价与输入规模相比如何？ 一个问题实例是一个单独的值，而我们的模型说值 \(n\) 的规模是 \(\log n\)。 因此，这是一个指数时间的算法！
注意，使用二进制表示时，很容易检查 2 整除 \(n\) 的次数。 那检查 3 整除 \(n\) 的次数呢？ 这就不那么容易了。 如果把 \(n\) 表示成三进制呢？ 那检查被 3 整除就容易了。
一般来说，是否存在多项式时间算法？ 我们不知道（而这一点对现代密码学至关重要， 它依赖于"分解大数需要很多时间"这一"事实"）。 但如果我们愿意接受一个概率算法呢？
以下是数论中的一些有用定理：
素数定理 ：小于 \(n\) 的素数个数为 （约）:math:frac{n}{ln n}。
小于 \(n\) 的素数之间的平均距离是 \(\ln n\)。
素因子分布定理 ：对大的 \(n\)， 平均而言，\(n\) 有大约 \(\ln \ln n\) 个不同的 素因子，标准差为 \(\sqrt{\ln \ln n}\)。 注意这是相当小的。 对 \(2^{32}\)，\(\log \log n = 5\)。
要证明一个数是合数，我们只需要一个因子。 而且，给定一个（声称的）因子，很容易验证这一声称 是否为真。 要证明一个数是素数需要什么呢？ 证明某个数是素数的难度远大于证明某个数是合数！ 因为我们需要检查的远不止一个值。
我们需要检查所有候选数（ \(\sqrt{n}\) ）是否为素数（ \(n\) ）的因子，以便确定（ \(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 检验的数往往 难以分解。 所以，即使使用了一个不是素数的数，它很可能仍会在 预期的用途上成功。
