用于测试确定性素数的 Miller-Rabin 的修改版本？
Modified version of Miller-Rabin to test deterministic primality?
Miller-Rabin test 使用 k 个随机整数来测试素数。
根据 CLRS，第 3rd 版，第 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.
那我们为什么不直接用 运行 random 测试 k 次，使用 different ( n - 1 ) / 2 个值并测试它们的素数？由于除 2 以外的所有素数都是奇数，并且没有见证人至少 ( n - 1 ) / 2 我们保证找到一个见证人（如果存在的话）。
运行 时间从 poly(log(n)) 到 n*poly(log(n))，这对于大数来说很糟糕，因为 n 比 log(n) 呈指数增长。
Miller-Rabin test 使用 k 个随机整数来测试素数。
根据 CLRS，第 3rd 版，第 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.
那我们为什么不直接用 运行 random 测试 k 次，使用 different ( n - 1 ) / 2 个值并测试它们的素数？由于除 2 以外的所有素数都是奇数，并且没有见证人至少 ( n - 1 ) / 2 我们保证找到一个见证人（如果存在的话）。
运行 时间从 poly(log(n)) 到 n*poly(log(n))，这对于大数来说很糟糕，因为 n 比 log(n) 呈指数增长。