这个问题实际上可能与 Miller-Rabin 素性测试程序无关;它可能只容易分析一些简单的伪代码。
在 CLRS (Introduction to Algorithms 3ed) 的第 969 页,介绍了 Miller-Rabin 的辅助函数:
WITNESS(a, n)
let t and u be such that t >= 1, u is odd, and n-1 = 2^t u
x_0 = MODULAR-EXPONENTIATION(a, u, n)
for i = 1 to t
x_i = x_{i-1}^2 mod n
if x_i == 1 and x_{i-1} != 1 and x_{i-1} != n-1
return TRUE
if x_t != 1
return TRUE
return FALSE
我完全从教科书中复制了以上内容。
现在,只知道MODULAR-EXPONENTIATION
返回 0 和 n-1 之间的结果,包括在内,我认为上面的伪代码完全等同于
WITNESS(a, n)
let t and u be such that t >= 1, u is odd, and n-1 = 2^t u
x_0 = MODULAR-EXPONENTIATION(a, u, n)
if x_0 == 1 or x_0 == n-1
return FALSE
else
return TRUE
如果是这样,那么原始实现可能还有其他问题,因为如果我没记错的话,Miller-Rabin 见证确实需要某种循环。有人可以提供一个简单的反例来证明我错了吗?