米勒拉宾Primality测试准确性

Question

我知道Miller-Rabin素性测试是概率性的.但是我想将它用于编程任务,不会留下任何错误.

如果输入数字是64位整数(即long long在C中),我们可以假设它是非常高的概率吗？

Answer 1

米勒 - 拉宾确实是概率性的,但你可以随意交换计算时间的准确性.如果您测试的数字是素数,它将始终给出正确的答案.有问题的情况是数字是复合数,但据报道是素数.我们可以使用维基百科上的公式来约束此错误的概率:如果您k随机选择不同的基数并测试它们,则错误概率小于4- ^k.所以,即便如此k = 9,你只有百万分之三的错误机会.并与k = 40左右就变得可笑的可能性不大.

也就是说,有一个确定性的米勒 - 拉宾版本,依赖于广义黎曼假设的正确性.对于最大为2 ⁶⁴的范围,只需检查即可a = 2, 3, 5, 7, 11, 13, 17, 19, 23.我有一个在线的C++实现,在许多编程竞赛中进行了现场测试.这是无符号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只是使用square-and-{multiply,add}在给定模数下乘以和取幂的基元.

Answer 2

对于n <2 ^ 64,可以对七个碱基2,325,9375,28178,450775,9780504和1795265022进行强伪试验,并完全确定n的素数; 看到http://miller-rabin.appspot.com/.

更快的素性测试对基数2执行强伪测试,然后进行Lucas伪调试.它只需要一次强伪测试的3倍,因此速度是7-base Miller-Rabin测试的两倍多.代码更复杂,但并不令人畏惧.

如果你有兴趣,我可以发布代码; 请在评论中告诉我.

Answer 3

在 Miller-Rabin 的每次迭代中，您需要选择一个随机数。如果你运气不好，这个随机数不会显示某些组合。一个小例子是2^341 mod 341 = 2，通过测试

\n\n

但测试保证它只让复合材料以 <1/4 的概率通过。因此，如果您使用不同的随机值运行测试 64 次，概率会降至 2^(-128) 以下，这在实践中就足够了。

\n\n

您应该查看Baillie\xe2\x80\x93PSW 素性测试。虽然它可能存在误报，但没有已知的示例，并且根据维基百科已验证，低于 2^64 的合数没有通过测试。所以它应该符合你的要求。

\n