java实现Miller-Rabin算法

import java.security.SecureRandom;


public class MillerRabin {

public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("2047\t"+MillerRabin(2047, 1));
        System.out.println("1203972837\t"+MillerRabin(1203972837, 1));
        System.out.println("65535\t"+MillerRabin(65535, 1));
    }
    /**
      *
      * @param n    The number should be tested whether it is a prime.
     * @param t
      * @return   
      *     true means n is a prime with a probability of (1/4)^t.
     *     false means n is a composite number with a probability of 1.
      */
    public static boolean MillerRabin(int n,int t)
     {       
         for(int i=0;i<t;i++)
            if(!isPrime(n))
               return false;
        return true;
     }
     /**
      *
      * @param n The number should be tested whether it is a prime.
      */
     public static boolean isPrime(int n)
    {
        int k,q;
        SecureRandom random=new SecureRandom();
        for(k=0;(((n-1)>>k)&1)==0;k++);
         q=(n-1)>>k;
         int a=random.nextInt(n);
       if(squareMultiply(a, q, n)==1)
             return true;
        for(int j=0;j<k;j++)
             if(squareMultiply(a, (int)Math.pow(2, j)*q,    n)==n-1)
                 return true;
        return false;
     }

     public static int squareMultiply(int a,int b,int p)
     {
        int x=1,y=a;
         int len=(int)Math.ceil((Math.log(b)/Math.log(2)));
        for(int i=0;i<len;i++)
         {
             if(((b>>i)&1)==1)
            {
                 x=(x*y)%p;
             }
            y=(y*y)%p;
        }
        return x;
     }

}