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

Question

Miller-Rabin test使用 k 个随机整数来测试素数。

根据 CLRS，第 3^rd 版，第 971 页:

Theorem 31.38

If n is an odd composite number, then the number of witnesses to the compositeness of n is at least (n - 1)/2.

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

Answer 1

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