Miller Rabin实现中的c-Bug

Question

我正在实现维基百科的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 : %dn",i,isPrime(i,k));
        }
        return 0;
}

Answer 1

如果基对候选者不是互质的，则强Fermat检验总是返回"不是可能素数"。

用你的错误

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

对于素数p，基与p（p的倍数）不是互质的，当且仅当rand()的结果具有形式

k*p + 1

对于小素数，即使只进行很少的迭代，也几乎可以保证会发生这种情况。

碱基应该在2和n/2之间（选择大于n/2的碱基是不必要的，因为a是复合性的见证，当且仅当n - a是一个），所以你想要类似的东西

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

如果你不介意随机数生成中的模偏差，它有利于小余数，或者

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

如果你想将偏差分布在整个可能的范围内。