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

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