2

ウィキペディアの Miller-Rabin アルゴリズムを実装していますが、漠然とした適切な結果が得られていないようです。7, 11, 19, 23 などは合成で報告されています。実際、k>12 の場合、5 であっても合成として表示されます。Miller-Rabin の背後にある数学を読みましたが、よく理解できておらず、盲目的にアルゴリズムに頼っています。私が間違っている場所の手がかりはありますか？

これが私のコードです：

#include<stdio.h>
#include<math.h>

int modpow(int b, int e, int m) {
    long result = 1;

    while (e > 0) {
        if ((e & 1) == 1) {
            result = (result * b) % m;
        }
        b = (b * b) % m;
        e >>= 1;
    }

    return result;
}

int isPrime(long n,int k){
        int a,s,d,r,i,x,loop;
        if(n<2)return 0;
        if(n==2||n==3)return 1;
        if(n%2==0)return 0;

        d=n-1;
        s=0;
        while(d&1==0){
                d>>=1;
                s++;
        }


        for(i=0;i<k;i++){
                loop=0;
                a=(int)(rand()*(n-1))+1;
                x=modpow(a,d,n);
                if(x==1 || x==n-1){
                        continue;

                }
                for(r=1;r<=s;r++){
                        x=modpow(x,2,n);
                        if(x==1)return 0;
                        if(x==n-1){
                                loop=1;
                                break;
                        }
                }
                if(!loop)return 0;

        }
        return 1; 

}

int main(){
        int i,k;
        scanf("%d",&k);
        for(i=5;i<100;i+=2){
                printf("%d : %d\n",i,isPrime(i,k));
        }
        return 0;
}
4

1 に答える 1

4

ベースが候補と互いに素でない場合、強力なフェルマーチェックは常に「確率的素数ではない」を返します。

あなたの間違いで

a=(int)(rand()*(n-1))+1;

素数の場合、の結果が次の形式である場合に限り、素数pは互いに素ではありませんp（の倍数）。prand()

k*p + 1

小さな素数の場合、それは数回の反復でも実際に発生することが保証されています。

ベースは2つのアンの間にある必要があります（1つである場合にのみ複合性の証人であるため、必要n/2以上に大きいベースを選択する）ので、次のようなものが必要です。n/2an - a

a = rand() % (n/2 - 2) + 2;

小さな剰余を優先する乱数生成のモジュロバイアスを気にしない場合、または

a = rand() /(RAND_MAX + 1.0) * (n/2 - 2) + 2;

可能な範囲全体にバイアスを分散させたい場合。

于 2012-08-03T17:59:10.750 に答える