Miller Rabin素性检验精度

Question

我知道Miller–Rabin primality test是概率型的。但是，我想将它用于一个不留错误空间的programming task。

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

Answer 1

对于n< 2^64，可以对7个碱基2、325、9375、28178、450775、9780504和1795265022执行强伪素性测试，并完全确定n的素性；请参阅http://miller-rabin.appspot.com/。

更快的素性测试对基数2执行强伪素数测试，然后执行Lucas伪素数测试。它需要的时间大约是单个强伪素性测试的3倍，因此速度是7碱基Miller-Rabin测试的两倍多。代码要复杂得多，但不会让人望而生畏。

如果你感兴趣，我可以发布代码；在评论中让我知道。

Answer 2

在米勒-拉宾的每次迭代中，你需要选择一个随机数。如果你不走运，这个随机数不会显示某些组合。这方面的一个小示例是2^341 mod 341 = 2，它通过测试

但是测试保证它只允许概率<1/4的组合通过。因此，如果使用不同的随机值运行测试64次，则概率降到2^(-128)以下，这在实践中已经足够了。

你应该看看Baillie–PSW primality test。虽然它可能有假阳性，但没有已知的例子，根据维基百科已经verified，没有低于2^64的综合数字通过测试。所以它应该能满足你的需求。

Answer 3

有64位值的MR测试的有效deterministic variants -不依赖于GRH -已经通过利用GPU和其他已知结果进行了详尽的测试。

我已经列出了我编写的一个C程序的相关部分，该程序测试任何64位值的原数：(n > 1)，使用Jaeschke和Sinclair的基础作为确定性的MR变体。它利用了gcc和clang的__int128扩展类型进行求幂。如果不可用，则需要显式例程。也许其他人会发现这很有用。

#include <inttypes.h>

/******************************************************************************/

static int sprp (uint64_t n, uint64_t a)
{
    uint64_t m = n - 1, r, y;
    unsigned int s = 1, j;

    /* assert(n > 2 && (n & 0x1) != 0); */

    while ((m & (UINT64_C(1) << s)) == 0) s++;
    r = m >> s; /* r, s s.t. 2^s * r = n - 1, r in odd. */

    if ((a %= n) == 0) /* else (0 < a < n) */
        return (1);

    {
        unsigned __int128 u = 1, w = a;

        while (r != 0)
        {
            if ((r & 0x1) != 0)
                u = (u * w) % n; /* (mul-rdx) */

            if ((r >>= 1) != 0)
                w = (w * w) % n; /* (sqr-rdx) */
        }

        if ((y = (uint64_t) u) == 1)
            return (1);
    }

    for (j = 1; j < s && y != m; j++)
    {
        unsigned __int128 u = y;
        u = (u * u) % n; /* (sqr-rdx) */

        if ((y = (uint64_t) u) <= 1) /* (n) is composite: */
            return (0);
    }

    return (y == m);
}

/******************************************************************************/

static int is_prime (uint64_t n)
{
    const uint32_t sprp32_base[] = /* (Jaeschke) */ {
        2, 7, 61, 0};

    const uint32_t sprp64_base[] = /* (Sinclair) */ {
        2, 325, 9375, 28178, 450775, 9780504, 1795265022, 0};

    const uint32_t *sprp_base;

    /* assert(n > 1); */

    if ((n & 0x1) == 0) /* even: */
        return (n == 2);

    sprp_base = (n <= UINT32_MAX) ? sprp32_base : sprp64_base;

    for (; *sprp_base != 0; sprp_base++)
        if (!sprp(n, *sprp_base)) return (0);

    return (1); /* prime. */
}

/******************************************************************************/

请注意，MR (sprp)测试略有修改，以传递迭代中的值，该迭代的基数是候选值的倍数，如网站的“备注”部分所述

更新：虽然这比Niklas' answer有更少的基础测试，但重要的是要注意，base：{3, 5, 7, 11, 13, 17, 19, 23, 29}提供了一个廉价的测试，允许我们排除超过：29 * 29 = 841的候选人-只需使用GCD即可。

对于(n > 29 * 29)，我们可以清楚地消除任何偶数作为质数的值。小素数的乘积：(3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29} = 3234846615，非常适合32位无符号值。gcd(n, 3234846615)比MR测试便宜多了！如果结果不是(1)，那么(n) > 841有一个很小的因素。

Merten's (?)定理表明，这个简单的gcd(u64, u64)测试消除了大约68%的奇数候选(作为复合)。如果你使用M-R来搜索素数(随机或递增)，而不仅仅是“一次性”测试，这当然是值得的！