我正在尝试制作RSA算法 . 为此，我需要rabin-miller见证模幂运算（至少我需要使用它） . 当我生成随机数来检查rabin miller它们是否为素数时问题就出现了，结果是非素数是rabin-miller算法的主要数字 . 有人可以帮我看看我失败的地方 . 提前致谢 .
int mod_exp(int a, int b, int n){
int d = 1,i,j=0;
int binary[15];
for(i=0;i<=15;i++){
binary[i] = -1;
}
i=0;
do{
binary[i]=(b%2);
if((b%2)==1)
b=(b-1)/2;
else
b=b/2;
i++;
}while(b!=0);
do{
d= (d*d)%n;
if(binary[i]==1)
d=(d*a)%n;
i--;
}while(i!=-1);
return d;
}
bool wittness(int a, int n){
int u=n-1,k=0;
long x, temp;
while(u%2== 0 ){
u=u/2;
k++;
}
x=mod_exp(a,u,n);
for(int i=1;i<=k;i++){
temp=x;
cout<< "primera x:"<<x<<endl;
x=long(x*x)%n;
cout<< "segunda x:"<<x<<endl;
if(x==1 && temp!=1 && temp != n-1)
return true;
}
if(x!=1)
return true;
return false;
}
bool miller_rabin(int n, int s){
int a,j;
srand(time(NULL));
for(j = 0; j<=s;j++){
a=rand()%s+1;
if(!wittness(a,n))
return false;
}
return true;
}
1 回答
我没有查看所有代码，但你的mod_exp函数肯定是不正确的 . 两个表达式
(d*d)%n和(d*a)%n都容易溢出，如果发生溢出，则会得到不正确的结果 .