CLRS中的miller-rabin伪码中是否存在严重的低效率？

Question

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

在CLRS的p 969 (算法3ED导论)上，给出了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之间的结果(包括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

对于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.：但是有一些方法可以减少计算的数量，你必须执行。证人分组已鉴定为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