米勒拉宾素性测试精度 [英] Miller Rabin Primality test accuracy

问题描述

我知道米勒 - 拉宾检验是概率性的。不过，我想用它不会留下任何闪失一个编程任务。

I know the Miller–Rabin primality test is probabilistic. However I want to use it for a programming task that leaves no room for error.

我们可以假定它是具有非常高的概率正确的，如果输入的号码是64位整数（即长长 C语言）？

Can we assume that it is correct with very high probability if the input numbers are 64-bit integers (i.e. long long in C)?

推荐答案

米勒罗宾确实是概率，但你可以换取计算时间精确度随意。如果测试数是素，它总是会给出正确的答案。有问题的情况是，当一个号码是复合材料，但据报道，素数。我们可以通过在维基百科上中的公式约束这种错误的概率：如果选择 K 不同碱基随机对其进行测试，误差概率小于4 ^-k 。因此，即使 K = 9 ，你只有在一个亿的机会被错误得到3。并与 K = 40 或使它成为可笑的可能性不大。

Miller–Rabin is indeed probabilistic, but you can trade accuracy for computation time arbitrarily. If the number you test is prime, it will always give the correct answer. The problematic case is when a number is composite, but is reported to be prime. We can bound the probability of this error using the formula on Wikipedia: If you select k different bases randomly and test them, the error probability is less than 4^-k. So even with k = 9, you only get a 3 in a million chance of being wrong. And with k = 40 or so it becomes ridiculously unlikely.

这是说，有一个<一个href=\"http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test\"相对=nofollow>米勒罗宾确定性版本，依托广义黎曼假设的正确性。对于范围ü
高达2 ⁶⁴ ，它足以检查 A = 2，3​​，5，7，11，13，17，19，23 。 我有一个C ++实现在线在很多这是现场测试编程竞赛。这里是模板为64位无符号整数一个实例：

That said, there is a deterministic version of Miller–Rabin, relying on the correctness of the generalized Riemann hypothesis. For the range u up to 2⁶⁴, it is enough to check a = 2, 3, 5, 7, 11, 13, 17, 19, 23. I have a C++ implementation online which was field-tested in lots of programming contests. Here's an instantiation of the template for unsigned 64-bit ints:

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 只是原语给定的模量下的繁殖和exponentiate，使用方 - 和 - {乘，加}

PowerMod and MultiplyMod are just primitives to multiply and exponentiate under a given modulus, using square-and-{multiply,add}.

这篇关于米勒拉宾素性测试精度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！