c - Miller-Rabin 无法工作 : problem with the base and the exponent

Question

我正在使用已知的强碱基 {2, 7, 61} 来求解 Miller-Rabin。假设我在这段代码中取 a = 2 和 n = 5 来测试它的素性。 n-1 的因式分解，即 4，是 2*2*1，所以我的 m 是 1。如果我测试 2^1 = x mod 5，我当然会得到 2，这将使我的 Miller-Rabin 测试失败，即使 5 是质数也是如此。

while(m > 0) {
        if(m%2 == 0) {
            pow *= a*a;
            pow %= n;
            m -= 2;
        }

        else {
            pow *= a;
            pow %= n;
            m -= 1;
        }
    }

    if(miller_rabin_single_base(pow, n) == 0) {
        return 0;
    }

...

我最后调用的方法只是检查 pow%n = 1 或 n-1。

不知道是我理解错了Miller-Rabin算法，还是代码有问题。该代码仅适用于某些素数。

我也是 C 新手，所以如果错误只是由错误的编码引起的，我深表歉意。

更新:

single_base 方法的声明:

int miller_rabin_single_base(int16 a, int16 n) {
    if(a%n == n-1 || a%n == 1) {
        return 1;
    }

    else {
        return 0;
    }
}

m和pow的声明:

int16 nmu = n-1;
int16 m;
int16 k = 0;
while((nmu/2)%2 == 0) {
    k++;
    nmu = nmu/2;
}

m = nmu/2;
k++;

int16 pow = 1;

int16 是一个 unsigned short，我用它来测试。

n 是可以运行代码的任何人选择的无符号短数。

如果我测试 n = 5、13 或 29，我得到它不是质数，但如果我测试 7、11 或 31，我得到它是质数:

./p_test miller 17
composite number

./p_test miller 23
prime number

Answer 1

您遗漏了一半的 M-R。给定见证 a=2 和 n=5 且 n-1=4 分解为 2²·1 你需要:

• 计算 a¹ mod n = 2 并与 1 和 n-1 (-1 mod n) 进行比较；如果等于任何一个，这个证人会说素数，然后你前进到下一个证人，但事实并非如此，而且你在 n-1 中有一个以上的因子 2，所以继续前进

• 计算 a^1·2 mod n = 4 并与 n-1 进行比较(仅，不是 1)；它是相等的，所以这个证人说质数；一般来说，你会前进到下一个证人(或者如果没有更多的人宣布 n 可能是质数)。如果不相等，因为您已经达到 k-1=1 个 2 的因数，您声明 n 复合并停止，但是对于包含更多 2 的因数的 n-1 个值，您将多次迭代此步骤。

在这种情况下，您的其他见证人是不必要的； 7 mod 5 = 2 所以它产生完全相同的结果，而 61 mod 5 = 1 和 1 作为证人说每个数都是质数，这是无用的。对于更现实(更大)的 n，它们会很有用。

注意计算a^m, a^m·2, a^m·2·2, a^{m·2·2 ·2} 等所有 mod n 可以通过首先计算 x = a^m mod n 然后重复计算 x = x² mod n 更有效地完成。

参见 example in wikipedia (尽管他们使用不同的变量名)。