c - Miller Rabin Primality 测试精度

Question

我知道 Miller–Rabin primality test是概率的。但是我想将它用于 programming task没有错误的余地。

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

Answer 1

Miller–Rabin 确实是概率论，但您可以任意用准确性换取计算时间。如果你测试的数字是素数，它总会给出正确答案。有问题的情况是一个数字是合数，但据报道是素数。我们可以使用 formula on Wikipedia 来限制这个错误的概率: 如果随机选择k个不同的碱基进行测试，错误概率小于4^-k。因此，即使 k = 9，您出错的几率也只有百万分之三。在 k = 40 左右，它变得非常不可能。

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

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 只是在给定模数下使用平方和-{multiply,add} 进行乘法和取幂的原语。