Miller-Rabin problem
Hi
Trying to code the miller-rabin primailty test, hit a problem and can't quite see where I am going wrong, err, help!
publicstaticboolean mr(BigInteger n,int t)throws Exception
{//Miller-Rabin Primality Test
srnd =new SecureRandom();
BigInteger s = n.subtract(ONE);
BigInteger r = ZERO;
BigInteger a = ZERO;
BigInteger y = ZERO;
while(s.mod(TWO).compareTo(ZERO)==0)
{
s = s.divide(TWO);
r = r.add(ONE);
}
for(int i = 1; i<=t; i++)
{
a =new BigInteger(n.subtract(TWO).bitCount(),srnd).add(TWO);
y = expm(a, r, n);
if(y.compareTo(ONE)!=0 && (y.compareTo(n.subtract(ONE))!=0))
{
BigInteger j = ONE;
while(j.compareTo(s.subtract(ONE))<=0 && y.compareTo(n.subtract(ONE))!=0)
{
y = expm(y, TWO, n);
if(y.compareTo(ONE)==0)
{
returnfalse;
}
j = j.add(ONE);
}
if(y.compareTo(n.subtract(ONE))!=0)
{
returnfalse;
}
}
}
returntrue;
}
Thanks
