フェルマーテストで素数判定

longの乱数が欲しかったのは、素数判定がやりたかったからなのですが、確認のためにエラトステネスの篩との比較をしたので、結局intの範囲までしか使いませんでした。
素数判定には、フェルマーテストを使います。で、今回は、わざと判定回数を少なくしてみて誤判定させています。
そうすると、こんな感じの実行結果になりました。

1729が素数と誤判定
8911が素数と誤判定
29341が素数と誤判定
46657が素数と誤判定
52633が素数と誤判定
75361が素数と誤判定

なんどか実行すると、誤判定が起きる数はいくつかに決まっていることがわかります。
この数は、カーマイケル数といいます。計算上で素数のようなふるまいをするので、擬素数ともいいます。

ソースはこんな感じ。

import java.util.Random;

public class PrimeCheck {
    public static void main(String[] args){
        r.nextLong();
        boolean[] comp = eratos(100000);
        for(int i = 9; i < comp.length; i += 2){
            if(fermatCheck(i, 8) == comp[i]){
                System.out.printf("%dが%sと誤判定%n", i, comp[i] ? "素数" : "合成数");
            }
        }
    }

    static Random r = new Random();

    /** エラトステネスの篩により合成数ならtrue/素数ならfalseの配列 */
    private static boolean[] eratos(int n){
        boolean[] ret = new boolean[n + 1];
        ret[0] = true;
        ret[1] = true;
        for(int i = 4; i <= n; i += 2){
            ret[i] = true;
        }
        for(int i = 3; i <= n; i += 2){
            if(ret[i]) continue;
            for(int j = i * 2; j <= n; j += i){
                ret[j] = true;
            }
        }
        return ret;
    }

    /** フェルマーテストによる素数判定 素数:true 合成数:false */
    private static boolean fermatCheck(int n, int c){
        for(int i = 0; i < c; ++i){
            if(n % 2 == 0) return false;//偶数なら合成数
            int a = r.nextInt(n - 2) + 2;//2以上n未満の値
            int g = (int) gcd(n, a);
            if(g != 1) return false;//最大公約数がみつかったなら合成数
            if(modPow(a, n - 1, n) != 1) return false;
        }
        return true;
    }

    /** (a ^ b) % m を計算 */
    static int modPow(int a, int b, int m){
        if(a == 0) return 0;

        int result = 1;
        a %= m;
        while(b != 0){
            if(b % 2 == 1){
                result = (int)(((long)result * a) % m);
            }
            a = (int)(((long)a * a) % m);
            b = b >> 1;
        }

        return result;
    }

    /** 最大公約数を求める(a > b) */
    private static long gcd(long a, long b){
        if(b == 0) return a;
        long m = a % b;

        return gcd(b, m);
    }
}

ちなみに、gcdやmodPowはBigIntegerに実装があるので、これを使うこともできますが、かなり遅くなります。まあ、それを言ってしまえば、確率的素数判定のメソッドisProbablePrimeというのもあるわけですが。
とりあえず、BigIntegerのメソッドを使うと、こうなります。

    private static boolean fermatCheck(int n, int c){
        for(int i = 0; i < c; ++i){
            if(n % 2 == 0) return false;//偶数なら合成数
            int a = r.nextInt(n - 2) + 2;//2以上n未満の値
            BigInteger ba = BigInteger.valueOf(a);
            BigInteger bn = BigInteger.valueOf(n);
            int g = bn.gcd(ba).intValue();
            if(g != 1) return false;//最大公約数がみつかったなら合成数
            if(!ba.modPow(bn, bn).intValue().equals(ba)) return false;
        }
        return true;
    }