6

我试图为Fermat primality test编写代码，但显然失败了。因此，如果我理解得很好： if pis prime then ((a^p)-a)%p=0where 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;
    }
4

3 回答 3

5

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

此外，正如 MattW 评论的那样，仅测试一个a不会给你一个关于候选人是否是素数的决定性答案。a在确定一个数字可能是素数之前，您必须测试许多可能的 s。即便如此，有些数字可能看起来是素数，但实际上是合数。

于 2013-03-14T16:47:20.867 回答
3

您正在处理非常大的数字，并尝试将它们存储在双精度数中，即只有 64 位。替身将尽其所能保持你的号码，但你会失去一些准确性。

另一种方法：

请记住，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;
}
于 2013-03-14T16:42:15.287 回答
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。如果使用上面显示的算法，没有中间结果会大于 1740 * 1740 = 3027600。但是如果先进行取幂，则中间结果为 437^13是 21196232792890476235164446315006597，你可能想避免。

即便如此，费马检验也不完美。有一些合数，即 Carmichael 数，无论您选择什么见证，它总是会报告质数。如果您想要更好的方法，请寻找 Miller-Rabin 测试。我谦虚地在我的博客上推荐这篇关于素数编程的文章。

于 2013-03-14T16:54:19.607 回答