ミラー・ラビン素数判定

目的

整数$n$が素数か合成数か、$1-4^{-k}$の確率で正しい判定を下します。

計算量

$O(k(\log n)^3)$

使い方

boolean isPrime(long n)
nが素数の時true、合成数の時falseをreturn

ソースコード

long[] prime_cand = new long[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };

boolean isPrime(long n) {
	if (n == 1)
		return false;
	if (n < isPrime.length) {
		return isPrime[(int) n];
	}
	if (n % 2 == 0)
		return false;

	long m = n - 1;
	int c = 0;
	while ((m & 1) == 0) {
		m >>= 1;
		++c;
	}
	out: for (int i = 0; i < prime_cand.length; ++i) {
		long a = prime_cand[i];
		a = pow_mod(a, m, n);
		boolean f = a == 1 || (c > 0 && a == n - 1);
		if (f)
			continue;
		for (int j = 0; j < c - 1; ++j) {
			a = mul_mod(a, a, n);
			f |= a == n - 1;
			if (f)
				continue out;
		}
		if (!f)
			return false;
	}
	return true;
}

long pow_mod(long a, long n, long mod) {
	long ret = 1;
	for (; n > 0; n >>= 1, a = mul_mod(a, a, mod)) {
		if ((n & 1) == 1) {
			ret = mul_mod(ret, a, mod);
		}
	}
	return ret;
}

long mul_mod(long a, long b, long mod) {
	long ret = 0;
	while (b > 0) {
		if (b % 2 == 0) {
			a <<= 1;
			if (a >= mod)
				a -= mod;
			b >>= 1;
		} else  {
			ret += a;
			if (ret >= mod)
				ret -= mod;
			a = a <<= 1;
			if (a >= mod)
				a -= mod;
			b >>= 1;
		}
	}
	return ret;
}