素数
素数就是只能被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
np 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;
}
}
