c - Miller Rabin Primality测试准确性

我知道Miller–Rabin primality test是概率性的。但是，我想将它用于programming task，不留任何错误的余地。

如果输入数字是64位整数(即C中的long long)，我们是否可以以很高的概率假设它是正确的？

最佳答案

Miller–Rabin确实具有概率性，但是您可以任意选择精度来计算时间。如果您测试的数字是质数，它将始终给出正确的答案。有问题的情况是数字是合成的，但据报道是质数。我们可以使用formula on Wikipedia来限制此错误的概率:如果您随机选择k不同的碱基并对其进行测试，则错误概率小于4-k。因此，即使使用k = 9，您也只有300万分之三的机会出错。加上k = 40左右，它变得不可思议。

就是说，有一个deterministic version of Miller–Rabin，依赖于广义Riemann假设的正确性。对于范围u
最多264，检查a = 2, 3, 5, 7, 11, 13, 17, 19, 23就足够了。 I have a C++ implementation online在许多编程竞赛中都经过了现场测试。这是无符号64位int模板的实例化:

bool isprime(uint64_t n) { //determines if n is a prime number
    const int pn = 9, p[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 };
    for (int i = 0; i < pn; ++i)
        if (n % p[i] == 0) return n == p[i];
    if (n < p[pn - 1]) return 0;
    uint64_t s = 0, t = n - 1;
    while (~t & 1)
        t >>= 1, ++s;
    for (int i = 0; i < pn; ++i) {
        uint64_t pt = PowerMod(p[i], t, n);
        if (pt == 1) continue;
        bool ok = 0;
        for (int j = 0; j < s && !ok; ++j) {
            if (pt == n - 1) ok = 1;
            pt = MultiplyMod(pt, pt, n);
        }
        if (!ok) return 0;
    }
    return 1;
}

PowerMod和MultiplyMod只是使用平方和{乘，加}在给定模数下进行乘和求幂的基元。

关于c - Miller Rabin Primality测试准确性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/24096332/