0

这个问题实际上可能与 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 见证确实需要某种循环。有人可以提供一个简单的反例来证明我错了吗？

4

2 回答 2

1

Miller-Rabin 素数测试被设计为 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 = 2andp = 5或a = 3and p = 7。实际上所有(p - 1, p)的元组都是反例。a^(n-1)所以没有捷径，你必须按照教科书的解释测试所有平方根。

PS：但是有一些方法可以减少计算次数，你必须执行。已为 n 确定了多达 3,317,044,064,679,887,385,961,981的见证人子集。因此，对于 n < 1,373,653，例如只需测试 a=2 和 a=3 就足够了。

于 2018-01-23T15:55:49.083 回答
0

对于书中的那个，我们有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
于 2018-01-23T20:00:44.483 回答