6

フェルマーの素数性テストのコードを書こうとしましたが、どうやら失敗しました。だから私がよく理解していれば：もし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;
    }
4

3 に答える 3

5

Fermat primality testに関するウィキペディアの記事を読むと、テストしている候補よりも少ないaものを選択する必要があります。

さらに、MattW がコメントしたように、1 つだけをテストしてaも、候補が優勢であるかどうかについて決定的な答えは得られません。a数がおそらく素数であると判断する前に、可能な s を多数テストする必要があります。それでも、いくつかの数は素数のように見えますが、実際には合成数です.

于 2013-03-14T16:47:20.867 に答える
3

非常に大きな数を扱っており、それらを倍精度で格納しようとしていますが、これはわずか 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;
}
于 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 を超える中間結果はありません。は 21196232792890476235164446315006597 です。

それでも、フェルマー検定は不完全です。カーマイケル数と呼ばれるいくつかの合成数があり、どの証人を選んでも常に素数を報告します。よりうまく機能するものが必要な場合は、Miller-Rabin テストを探してください。私のブログで、素数を使ったプログラミングに関するこのエッセイを適度にお勧めします。

于 2013-03-14T16:54:19.607 に答える