费马素性检验

Question

我曾尝试为Fermat primality test编写代码，但显然失败了。所以如果我理解的很好:如果p是质数，那么((a^p)-a)%p=0其中就是p%a!=0。我的代码看起来没问题，因此很可能是我误解了基础知识。这里我漏掉了什么？

private bool IsPrime(int candidate)
    {
        //checking if candidate = 0 || 1 || 2
        int a = candidate + 1; //candidate can't be divisor of candidate+1
        if ((Math.Pow(a, candidate) - a) % candidate == 0) return true;
        return false;
    }

Answer 1

阅读Fermat primality test上的维基百科文章，您必须选择一个小于您正在测试的候选人的a，而不是更多。

此外，正如MattW评论的那样，只测试一个a不会给你一个关于候选者是否是质数的确凿答案。您必须测试许多可能的a，然后才能确定一个数字可能是质数。即使这样，some numbers看起来可能是质数，但实际上是复合的。

Answer 2

您正在处理非常大的数字，并试图以双精度存储它们，这只有64位。double将尽其所能保持您的数字，但您将失去一些准确性。

另一种方法：

请记住，mod运算符可以多次应用，但仍然会产生相同的结果。因此，为了避免得到大量的数字，你可以在计算你的功率时应用mod运算符。

类似于：

private bool IsPrime(int candidate)
{
    //checking if candidate = 0 || 1 || 2
    int a = candidate - 1; //candidate can't be divisor of candidate - 1

    int result = 1;
    for(int i = 0; i < candidate; i++)
    {
        result = result * a;

        //Notice that without the following line, 
        //this method is essentially the same as your own.
        //All this line does is keeps the numbers small and manageable.
        result = result % candidate;
    }

    result -= a;
    return result == 0;
}

Answer 3

您的基本算法是正确的，但是如果您想对非平凡数字执行此操作，则必须使用比int更大的数据类型。

你不应该以这种方式实现模幂运算，因为中间结果是巨大的。下面是模幂运算的平方乘法算法：

function powerMod(b, e, m)
    x := 1
    while e > 0
        if e%2 == 1
            x, e := (x*b)%m, e-1
        else b, e := (b*b)%m, e//2
    return x

例如，437^13 (mod 1741) = 819。如果您使用上面所示的算法，则中间结果不会大于1740x1740= 3027600。但是如果首先执行求幂，437^13的中间结果是21196232792890476235164446315006597，这可能是您想要避免的。

即便如此，费马测试仍然是不完美的。有一些复合数，Carmichael数，无论你选择什么证人，它总是会报告质数。如果你想要更好的效果，可以看看Miller-Rabin测试。在我的博客中，我谦虚地推荐使用质数编程的this essay。