Miller-Rabin测试怪现象??
不知是我写错了，还是本来如此，发现65537居然不能通过以3为底的测试。请教！
我的java代码如下：
boolean IsPrime(int N){
int[] primes =new int[]{2,3,5,7,11}; /底，据说2^32以内的数用这5个底就可以了
if(N<13){
if(N==2 || N==3 || N==5 || N==7 || N==11){
return true;
}else{
return false;
}
}
if(N % 2==0)return false;//不加这句的话，下面紧接着的循环会出错
int m=N-1;int j=0;
while(m % 2==0){ ;//此循环计算(2^j)*m=N-1;
m/=2;
j++;
}
for(int i=0;i<5;i++){
int v=PowMod(primes,m,N);//模幂算法
;//v=1，可能是素数，跳过
if(v!=1){;//v不等于1，可能不是素数。
int k=1;
while(v!=N-1){
if(k==j)return false;//一定不是素数，返回false
k++;
v*=v;
v%=N;
}
;//运行到这里，说明v=N-1，可能是素数，跳过
}
;//运行到这里，说明第i次测试可能是素数
}
;//运行到这里，说明在2^32内一定是素数
return true;
}
后来，我把代码改成了这样，就通过了：
boolean IsPrime(int N){
int[] primes =new int[]{2,3,5,7,11};
if(N<13){
if(N==2 || N==3 || N==5 || N==7 || N==11){
return true;
}else{
return false;
}
}
for(int i=0;i<5;i++){
int v=PowMod(primes,N-1,N);
if(v!=1 && v!=N-1){
return false;
}
}
return true;
}
请问为什么？ 素数怎么可能通不过,肯定是你程序问题了,你下载个RSA1.0的对照一下就知道错在哪了 你的代码中含有“v*=v;”，
请检查一下是否有溢出之可能，
比如当 v=65536 时，v*=v 结果会是什么？（32位int型） int v=PowMod(primes,m,N);//模幂算法
int v=PowMod(primes,N-1,N);
这里的m跟N-1值是完全不同,在上式中m的值是1,在下式中m的值是65536 可能是v*v溢出了，谢谢3楼！ 谢谢，刚刚把int v改成long v，果然没问题了！谢谢gxqcn！ 防止“溢出”，不仅仅是加减法，还有乘法等，
此类错误，编译器不会给你任何警告，
但开发者必须做到心中有数，避免数据出现意料外的“回绕”。
页:
[1]