素数

素数就是只能被1和其自身整除，且大于1的自然数
RSA算法中用到大素数

判断n是否为素数，简单的方法是将n按顺序除以比2大的数字，看是否能被整除（n%m==0）

public class Prime {

    private boolean isPrime(int n) {
        if (n <= 1 || (n != 2 && ((n & 1) == 0))) {
            return false;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

费马小定理

p = 素数
n < p
n^p mod p = n
对于任意素数p，上面事务公式都成立

public class Prime {

    /**
     * 根据费马小定理判断是否为素数
     * @param n 输入整数
     * @param k 最大循环次数
     * @return
     */
    private static boolean isPrime(int n, int k) {
        if (n <= 1 || (n != 2 && ((n & 1) == 0))) {
            return false;
        }

        while (k > 0) {
            int rand = (int) (Math.random() * n);
            if (Math.pow(rand, n) % n != rand) {
                return false;
            }
            k--;
        }
        return true;
    }
}