A simple Miller-Rabin prime number test I wrote in Java.
Along with this method I implemented isWitness as well as the modulo power by bit shifting method.
Feel free to comment ;)
=================
Update:
Someone requested for myBigRanNum and FactorOfTwo, I put them here as well, enjoy.
=================
[code]public static boolean MillerRabin(BigInteger n, int k){
BigInteger a;
BigInteger m = n.subtract(BigInteger.ONE);
boolean isPrime = true;
if (n.compareTo(BigInteger.ONE) == 0) return false;
if (n.mod(BigInteger.valueOf(2)).intValue() == 0) return false;
for (int i = 0; i < k; i++) {
a = myBigRanNum(MAX_BIT);
if (a.compareTo(m) > 0) a = a.mod(m);
if (a.compareTo(BigInteger.ZERO) == 0) a = BigInteger.ONE;
if (isWitness(a, n)) return false;
}
return isPrime;
}
public static boolean isWitness(BigInteger a, BigInteger n) {
int s;
BigInteger apow;
BigInteger firstEqua, secondEqua;
BigInteger m = n.subtract(BigInteger.ONE);
BigInteger d;
s = FactorOfTwo(m);
d = m.divide(BigInteger.valueOf((int)Math.pow(2, s)));
firstEqua = ModExpo(a, d, n);
if (firstEqua.intValue() == 1 || firstEqua.compareTo(m) == 0 ) return false;
for (int r = 0; r < s; r++) {
apow = d.multiply(BigInteger.valueOf((int)Math.pow(2, r)));
secondEqua = ModExpo(a, apow, n);
if (secondEqua.intValue() == -1 || secondEqua.compareTo(m) == 0) {
return false;
}
}
return true;
}
public static BigInteger ModExpo(BigInteger aBigInt, BigInteger pow, BigInteger n) {
BigInteger e = pow;
BigInteger a = aBigInt;
BigInteger result = BigInteger.ONE;
while (e.compareTo(BigInteger.ZERO) > 0 ) {
if (e.and(BigInteger.ONE).compareTo(BigInteger.ONE) == 0 ){
result = (result.multiply(a)).mod(n);
}
e = e.shiftRight(1);
a = (a.multiply(a)).mod(n);
}
return result;
}
public static int FactorOfTwo(BigInteger aNumber) {
int i = 0;
BigInteger myNumber = aNumber;
BigInteger myRemainer;
while (true) {
myRemainer = myNumber.mod(BigInteger.valueOf(2));
if (myRemainer.compareTo(BigInteger.ZERO) != 0 ) break;
myNumber = myNumber.divide(BigInteger.valueOf(2));
i++;
}
return i;
}
public static BigInteger myBigRanNum(int numBits) {
//We only deal with positive number here
BigInteger aBigInterger = new BigInteger(numBits, aRand);
aBigInterger = aBigInterger.abs();
return aBigInterger;
}[/code]
