Miller Rabin Algorithm
Hi,
I wrote the following code for Miller Rabin algorithm:
publicstaticvoid main(String[] args){
MillerRabin test =new MillerRabin();
test.test_prime(221,5,2,55);
}
publicvoid test_prime(int n,int a,int k,int q){
if( (int)(Math.pow(a,q)) % n == 1 )
System.out.println(a+"^"+q+"%"+n+"==1\t"+"Maybe prime*.");
for(int j=0; j<= (k-1); j++ ){
int t = (int) Math.pow(2,j);
int comp = (int)Math.pow(a,(t*q)) % n;
if( comp == (n-1))
System.out.println(a+"^("+t+"*"+q+")%"+n+"=="+(n-1)+"\t"+"Maybe prime.");
else{
int tmp = (int) (Math.pow(a,(t*q)) % n);
System.out.println(a+"^("+t+"*"+q+")%"+n+"=="+tmp+"\t"+"Composite.");}
}
}
Output:
5^(1*55)%221==178Composite.
5^(2*55)%221==137Composite.
But running the code gives wrong results. For 5^(1*55)%221==178 it should be == 112. Any help?
# 1
> ...
> But running the code gives wrong results. For
> 5^(1*55)%221==178 it should be == 112. Any help?
5^55 cannot be represented by any of Java's primitive data types (too large).
PS. You can have a look at the source code of BigInteger's isProbablePrime(...), which makes use of Miller-Rabin's primality test among others (if memory serves me well).
# 3
Your loop is basically finding the sequence of values pow(a,q*pow(2,j)) for incrementing j. Now, pow(a,q*pow(2,j+1)) == pow(a,q*pow(2,j)*2) == pow(pow(a,q*pow(2,j)),2). Therefore you can calculate curr incrementally by repeatedly squaring the previous value. Multiplication is well-behaved with respect to modulo operations, so you can change your code from for( int j=0; j<= (k-1); j++ ){
int t = (int) Math.pow(2,j);
int comp = (int)Math.pow(a,(t*q)) % n;
// Test
}
to int comp=pow(a,q)%n;
for( int j=0; j<= (k-1); j++ ){
// Test
comp = (comp*comp) % n;
}
Then the only risk is that the pow(a,q) will overflow. Again, apply the nice behaviour of multiplication and write your own public static int powmod(int a, int q, int n)
method. That's not much different from a common exercise given to students in their first week, so I won't provide an implementation here.
