algorithm - Miller-Rabin 的修改版本来测试确定性素数？

Question

Miller-Rabin 检验使用k个随机整数来检验素数。

根据 CLRS，第 3^版，第 971 页：

定理 31.38

如果 n 是一个奇合数，那么见证 n 的复合性的人数至少为 (n - 1)/2。

那么我们为什么不直接运行k 次随机测试，而是使用不同的(n - 1) / 2 值并测试它们的素数呢？由于除了 2 之外的所有素数都是奇数，并且没有见证人至少是 (n - 1) / 2，因此我们保证如果存在就可以找到见证人。

Answer 1

运行时间从 poly(log(n)) 变为 n*poly(log(n))，这对于大数来说很糟糕，因为 n 比 log(n) 大得多。