我知道米勒-拉宾素数检验是概率性的。但是，我想将它用于不留任何错误空间的编程任务。
long long如果输入数字是 64 位整数（即在 C 中），我们可以假设它是正确的吗？
问问题
7449 次
5 回答
12
Miller-Rabin 确实是概率性的，但您可以任意用准确性换取计算时间。如果你测试的数字是素数，它总是会给出正确的答案。有问题的情况是当一个数字是复合的，但据报道是素数。我们可以使用维基百科上的公式来限制这个错误的概率：如果你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只是在给定模数下乘以和取幂的基元，使用平方和-{multiply,add}。
于 2014-06-07T11:27:31.153 回答
6
对于n < 2^64，可以对2、325、9375、28178、450775、9780504、1795265022这7个碱基进行强伪素检验，完全确定n的素数；看http://miller-rabin.appspot.com/。
更快的素数检验对基数 2 执行强伪素检验，然后是卢卡斯伪素检验。它需要的时间大约是单个强伪素测试的 3 倍，因此比 7 碱基米勒拉宾测试快两倍多。代码更复杂，但并不令人生畏。
如果您有兴趣，我可以发布代码；在评论中告诉我。
于 2014-06-07T11:51:11.337 回答
1
在 Miller-Rabin 的每次迭代中，您需要选择一个随机数。如果你不走运，这个随机数不会显示某些组合。一个小例子就是2^341 mod 341 = 2，通过测试
但是该测试保证它只让复合通过的概率<1/4。因此，如果您使用不同的随机值运行 64 次测试，概率会降至 2^(-128) 以下，这在实践中就足够了。
你应该看看Baillie-PSW primality test。虽然它可能有误报，但没有已知的例子，根据维基百科已经证实，没有低于 2^64 的合数通过测试。所以它应该符合你的要求。
于 2014-06-07T11:07:27.943 回答
1
64 位值的 MR 测试有一些有效的确定性变体——它们不依赖于 GRH——已经通过利用 GPU 和其他已知结果进行了详尽的测试。
我列出了我编写的用于测试任何 64 位值的素数的 C 程序的相关部分：(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 的答案有更少的基础测试，但重要的是要注意基础：{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 位无符号值。Agcd(n, 3234846615)比 MR 测试便宜很多！如果结果不是 (1)，则(n) > 841有一个小因素。
Merten (?) 定理表明，这个简单的gcd(u64, u64)测试消除了约 68% 的奇数候选（作为复合材料）。如果您使用 MR 搜索素数（随机或增量），而不仅仅是“一次性”测试，这当然值得！
于 2016-03-06T09:45:46.677 回答
-1
你的电脑并不完美；它有一个有限的失败概率，导致计算不正确。如果 MR 测试给出错误结果的概率大大低于其他计算机故障的概率，那么你就可以了。没有理由将 MR 测试运行少于 64 次迭代（2 ^ 128 中的 1 次错误机会）。大多数示例在最初的几次迭代中都会失败，因此只有实际的素数会被彻底测试。使用 128 次迭代以获得 1 in 2^256 的错误机会。
于 2014-06-07T12:43:22.397 回答