米勒拉宾Primality测试准确性
我知道Miller-Rabin素性测试是概率性的。 但是，我想将它用于编程任务 ，不会留下任何错误。
如果输入数字是64位整数（即C long long ），我们可以假设它是非常高的概率吗？
米勒 – 拉宾确实是概率性的，但你可以随意交换计算时间的准确性。 如果您测试的数字是素数，它将始终给出正确的答案。 有问题的情况是数字是复合的，但据报道是素数。 我们可以使用维基百科上的公式来约束此错误的概率：如果您随机选择k不同的基数并对其进行测试，则错误概率小于4- k 。 因此，即使k = 9 ，你只有百万分之三的错误机会。 并且当k = 40左右时，它变得非常不可能。
也就是说，有一个确定性的米勒 – 拉宾版本 ，依赖于广义黎曼假设的正确性。 对于范围u到2 64 ，足以检查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}在给定模数下乘法和取幂的基元。
对于n <2 ^ 64，可以对七个碱基2,325,9375,28178,450775,9780504和1795265022进行强伪试验，并完全确定n的素数; 见http://miller-rabin.appspot.com/ 。
更快的素性测试对基数2进行强伪测试，然后进行Lucas伪次数测试。 它只需要一次强伪测试的3倍，因此速度是7-base Miller-Rabin测试速度的两倍多。 代码更复杂，但并不令人畏惧。
如果你有兴趣，我可以发布代码; 请在评论中告诉我。
在Miller-Rabin的每次迭代中，您需要选择一个随机数。 如果你运气不好，这个随机数字不能揭示某些复合材料。 一个小例子是2^341 mod 341 = 2 ，通过测试
但是测试保证它只允许复合通过概率<1/4。 因此，如果您使用不同的随机值运行测试64次，则概率降至2 ^（ - 128）以下，这在实践中已足够。
您应该看看Baillie-PSW素性测试 。 虽然它可能有误报，但是没有已知的例子，并且根据维基百科已经证实没有低于2 ^ 64的复合数通过测试。 所以它应该符合您的要求。
对于64位值的MR测试存在有效的确定性变体 – 它们不依赖于GRH – 已经通过利用GPU和其他已知结果进行了详尽的测试。
我已经列出了我编写的C程序的相关部分，它测试任何64位值的原始性： (n > 1) ，使用Jaeschke和Sinclair的确定性MR变量的基础。 它利用gcc和clang的__int128扩展类型进行求幂。 如果不可用，则需要明确的例程。 也许其他人会觉得这很有用……
#include /******************************************************************************/ 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 st 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的答案少，但重要的是要注意基础： {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的（？）定理表明，这个简单的gcd(u64, u64)测试消除了所有奇数候选者（作为复合物）的约68％。 如果你使用MR搜索质数（随机或递增），而不仅仅是“一次性”测试，这当然是值得的！
你的电脑并不完美; 它具有有限的失败概率，从而导致计算结果不正确。 提供MR测试给出错误结果的概率远小于其他一些计算机失败的概率，那么你就没事了。 没有理由在少于64次迭代的情况下运行MR测试（误差为1 ^ 2 ^ 128）。 大多数示例在前几次迭代中都会失败，因此只有实际的质数才会被彻底测试。 使用128次迭代获得1 in 2 ^ 256的错误机会。