Miller-Rabin测试怪现象??

ssikkiss

不知是我写错了，还是本来如此，发现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[i],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[i],N-1,N); if(v!=1 && v!=N-1){ return false; } } return true; } 请问为什么？

qianyb

素数怎么可能通不过,肯定是你程序问题了,你下载个RSA1.0的对照一下就知道错在哪了

gxqcn

你的代码中含有“v*=v;”， 请检查一下是否有溢出之可能， 比如当 v=65536 时，v*=v 结果会是什么？（32位int型）

qianyb

int v=PowMod(primes[i],m,N);//模幂算法 int v=PowMod(primes[i],N-1,N); 这里的m跟N-1值是完全不同,在上式中m的值是1,在下式中m的值是65536

ssikkiss

可能是v*v溢出了，谢谢3楼！

ssikkiss

谢谢，刚刚把int v改成long v，果然没问题了！谢谢gxqcn！

gxqcn

防止“溢出”，不仅仅是加减法，还有乘法等， 此类错误，编译器不会给你任何警告， 但开发者必须做到心中有数，避免数据出现意料外的“回绕”。