class MillerRabinTest

gistfile1.java

class MillerRabinTest{
	public static boolean isPrime(int n, int k) {
		if (n == 2) {
			return true;
		}
		if (n == 1 || n % 2 == 0) {
			return false;
		}
		int d = (n - 1) / 2;
		int s = 0;
		while (d % 2 == 0) {
			d = d / 2;
			s++;
		}
		for (int i = 0; i < k; i++) {
			boolean isP = false;
			int a = (int)(Math.round((n - 2) * Math.random()) + 1);
			int r = powMod(a, d, n);
			if (r == 1 || r == n - 1) {
				isP = true;
			}
			r = powMod(r, 2, n);
			for (int j = 0; j < s; j++) {
				if (r == n - 1) {
					isP = true;
				}
				r = powMod(r, 2, n);
			}
			if (!isP) {
				return false;
			}
		}
		return true;
	}
	private static int powMod(long base, long power, long mod) {
		long result = 1;
		while (power > 0) {
			if (power % 2 == 1) {
				result = (result * base) % mod; 
			}
			base = (base * base) % mod;
			power = power / 2;
		}
		return (int)result;
	}
}