0

我正在尝试调试标准（即概率）Miller-Rabin 测试的实现。这是现在的代码，在方法中执行了基本的测试main：

#include <iostream>
#include <random>

typedef unsigned long long int ulli;
std::random_device rd;
std::mt19937_64 mt(rd());

ulli upow(ulli x, ulli y) {
    if (y == 0)
        return 1;
    else if (y == 1)
        return x;
    else if (y % 2 == 0)
        return upow(x*x, y/2);
    else
        return x * upow(x*x, (y-1)/2);
}

bool miller_rabin(ulli n, ulli d) {
    std::uniform_int_distribution<ulli> dist(2, n-2);

    ulli a = dist(mt);
    ulli x = upow(a, d) % n;
    if (x == 1 || x == n - 1)
        return true;

    while (d != n - 1) {
        x = x*x % n;
        d *= 2;
        if (x == 1)
            return false;
        if (x == n - 1)
            return true;
    }

    return false;
}

bool is_prime(ulli n, ulli k) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0)
        return false;

    ulli d = n - 1;
    while (d % 2 == 0)
        d /= 2;

    for (int i = 0; i < k; ++i) {
        if (!miller_rabin(n, d))
            return false;
    }

    return true;
}


int main() {
    ulli tests = 30;

    std::cout << "is_prime(2): " << is_prime(2, tests) << std::endl;
    std::cout << "is_prime(10): " << is_prime(10, tests) << std::endl;
    std::cout << "is_prime(97): " << is_prime(97, tests) << std::endl;
    std::cout << "is_prime(256): " << is_prime(256, tests) << std::endl;
    std::cout << "is_prime(179424691): " << is_prime(179424691, tests) << std::endl;
    std::cout << "is_prime(32416187563): " << is_prime(32416187563, tests) << std::endl;
}

我目前遇到的问题是：最后两个测试返回错误，这（因为它们都是素数）应该是不可能的。即使我通过了尽可能多的测试，is_prime仍然输出错误。

在这一点上，我真的不知道出了什么问题。有任何想法吗？

4

0 回答 0