CLRS 中的这个 miller-rabin 伪代码是否效率低下？

Question

这个问题实际上可能与 Miller-Rabin 素性测试程序无关；可能只是简单的分析一些简单的伪代码。

在 CLRS 的第 969 页（算法导论第 3 版）中，介绍了 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 returns 是介于 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 见证了是否需要某种循环。有人可以提供一个简单的反例来证明我错了吗？

Answer 1

Miller-Rabin primality test 设计为 TRUE，因为 n 是素数，因此返回 FALSE 应该只适用于合数。让我们用一个 Python 小程序来测试一下。

def wrongwitness(a, n):             #implementation of your shortcut
    u = n - 1
    t = 0
    while u % 2 == 0:               #n - 1 = 2^t * u
        u //= 2
        t += 1

    x_0 = pow(a, u, n)              #x0 = a ^ u (mod n), oops, where is t?

    if x_0 == 1 or x_0 == n - 1:
        return False
    else:
        return True

primes = [5, 7, 11, 13, 17, 19, 23, 29, 31]

for p in primes:         
    for a in range(2, p):           #1 < a < p
        if not wrongwitness(a, p):  #witness returned FALSE, though we have a prime number
            print("Found counter example: a = ", a, "and p = ", p )

这为我们提供了很多小至 a = 2 和 p = 5 或 a = 3 和 p = 7 的快捷方式实施的反例。实际上所有 (p - 1, p) 元组都是反例。所以没有捷径，您必须按照课本中的说明测试 a^(n-1) 的所有平方根。

P.S.: 但是有办法减少计算次数，你必须执行。 Subsets of witnesses 已被识别为 n 最多 3,317,044,064,679,887,385,961,981。因此，对于 n < 1,373,653，仅测试 a=2 和 a=3 就足够了。

Answer 2

对于书中的那个，我们有WITNESS(2, 5) == FALSE

对于快捷方式，我们有WITNESS(2, 5) == TRUE，因此快捷方式是错误的。

顺便说一下，下面的替代实现是有效的，并且在所有情况下当它找到 x_i == 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)
    for i = 1 to t
        x_i = x_{i-1}^2 mod n
        if x_i == 1 
            if x_{i-1} != 1 and x_{i-1} != n-1
                return TRUE
            else
                return FALSE
    return TRUE

CLRS 中的这个 miller-rabin 伪代码是否效率低下？

is there a major inefficiency in this miller-rabin pseudocode in CLRS?

algorithm

primes

code-analysis

pseudocode

primality-test