Miller-Rabin素数判定法の実装(Java)

ミラー-ラビン素数判定法 - Wikipedia
http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC-%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95

少なくとも5桁くらいまでの整数は正確に判定できると思います。

MillerRabinTest.java

// Miller-Rabin素数判定クラス
class MillerRabinTest{

    // nが素数ならtrue、nが合成数ならfalseを返す
    // kは判定サイクル数で、kが大きいほど素数判定が正確になり、速度は低下する。
    public static boolean isPrime(int n, int k) {
        // 2は素数
        if (n == 2) {
            return true;
        }
        // 1は素数ではない
        // 2以外の偶数は素数ではない
        if (n == 1 || n % 2 == 0) {
            return false;
        }
        // n-1を2のべき乗で割って2^s*dの形式に変形
        int d = n - 1;
        int s = 0;
        while (d % 2 == 0) {
            d = d / 2;
            s++;
        }
        // 判定サイクル
        for (int i = 0; i < k; i++) {
            boolean isPP = false;
            // 1からn-1の範囲から整数aをランダムに選ぶ
            int a = (int) (Math.round((n - 2) * Math.random()) + 1);
            // a^d mod n が1もしくはn-1なら、nはprobably prime
            int r = modPow(a, d, n);
            if (r == 1 || r == n - 1) {
                isPP = true;
            }
            // r^2 mod n が-1なら、nはprobably prime
            for (int j = 0; j < s; j++) {
                r = modPow(r, 2, n);
                if (r == n - 1) {
                    isPP = true;
                }
            }
            // 上記のどちらにも当てはまらない場合、nはcomposite
            if (!isPP) {
                return false;
            }
        }
        return true;
    }

    // べき剰余の計算
    private static int modPow(long x, int k, int m) {
        if (k == 0) {
            return 1;
        }
        if (k % 2 == 0) {
            return modPow(x * x % m, k / 2, m);
        } else {
            return (int) (modPow(x, k - 1, m) * x % m);
        }
    }
}