El Gamal signature -Handle big integer

[miotvsingtel]

For those who understand El Gamal signature scheme . U may have known the verification process of the signature :

y^a *a^b (mod p ) = g^M (mod p)

We have to compute both side of the equation. If they are equal, the signature is verified.

but i have issue computing g^M since M after MD5 hashing is a 128 bit number. IT seems g to the power of M is computational infeasible
!!!!!!!!!!!!!!!!

Any one have solution for it ?

Below is my code. the number are just taken as example:

package Server;
import java.math.*;

public class Checkup {

BigInteger left,right,
one=new BigInteger("1"),
p=new BigInteger("17"),
k=new BigInteger("11"),
g=new BigInteger("7"),
m,a,b,y,x;
int k1=k.intValue(),x1,a1,b1,m1,left1,right1;
public Checkup(String str,String xx){
m = new BigInteger(str,16);
x = new BigInteger(xx);
x1=x.intValue();
}

boolean Docheck(){
a=(g.pow(k1)).remainder(p);
y=(g.pow(x1)).remainder(p);
b=m.subtract(x.multiply(a)).divide(k).remainder(p. subtract(one));
a1=a.intValue();b1=b.intValue();m1=m.intValue();
left = y.pow(a1).multiply(a.pow(b1)).remainder(p);

right= g.pow(m1).remainder(p);
left1=left.intValue();
right1=right.intValue();
if(left1==right1)
return true;
return false;
}
}

[miotvsingtel]

please help !:@

package Server;
import java.math.*;

public class Checkup {

BigInteger left,right,
one=new BigInteger("1"),
p=new BigInteger("17"),
k=new BigInteger("11"),
g=new BigInteger("7"),
m,a,b,y,x;
int k1=k.intValue(),x1,a1,b1,m1,left1,right1;
public Checkup(String str,String xx){
m = new BigInteger(str,16);
x = new BigInteger(xx);
x1=x.intValue();
}

boolean Docheck(){
a=(g.pow(k1)).remainder(p);
y=(g.pow(x1)).remainder(p);
b=m.subtract(x.multiply(a)).divide(k).remainder(p. subtract(one));
a1=a.intValue();b1=b.intValue();m1=m.intValue();
left = y.pow(a1).multiply(a.pow(b1)).remainder(p);

right= g.pow(m1).remainder(p);
left1=left.intValue();
right1=right.intValue();
if(left1==right1)
return true;
return false;
}
}

[quuba]

Fast exponentiation algorithm:
http://pl.wikipedia.org/wiki/Algorytm_szybkiego_potęgowania
and lines 27-31 you can replace by

return left.equals(right);