关于java:素数判定-高级程序员才知道的那些事儿

在信息安全畛域，常常须要用到一些大素数，比方驰名的 RSA 算法就必须依赖到两个大素数。侥幸的是自然数中素数还真不少(很简略就能证实素数有无穷多个)，而且密度也不算低，所以找到一个素数不是那么难，但让你找一个能用在 RSA 算法里的素数就比拟难了。

试想下，如果当初让你去寻找出一个素数，你会怎么办？记得刚上大学刚学会 C 语言根本语法后，有道课后题就是 断定一个数是否是素数，具备根本编程能力的人肯定能写出如下代码：

boolean checkPrime(int n) {for (int i = 2; i*i <= n; i++) {if (n%i == 0) {return false;}
    }
    return true;
}

素数断定最简略的办法就是试除，也就是下面代码。它的原理是从 2 到根号 n，看 n 是否能被某个数除尽，如果能那 n 必定不是素数，反之肯定是素数。这的确是个简略粗犷且正确的办法，惟一的问题是它太慢了，断定一个数的工夫复杂度是 O(n)。如果让你用这种办法去判断一个几百位的数是否是素数，那可能用当初最先进的计算机，也须要 n 多年能力算进去。

当然素数断定还有一个更快的批量断定算法——埃氏筛选 ，他找到 n 以内的所有素数只须要O(n log log n) 的工夫复杂度。

其原理是这样的，设置一个标记数组，开始先把 2 的所有倍数都标记了，而后往后走发现 3 没有被标记，那 3 必定是个素数，而后在标记数组中把所有 3 的倍数标记掉，而后发现 4 曾经被标记了跳过，到 5……，直到标记完所有数字，那么剩下未标记的数字就是素数了，见上图，代码如下：

int[] signs = new int[n+1];
void eratosthenes(int n) {for (int i = 2; i <= n; i++) {if (signs[i] == 0) {for (int j = i * i; j <= n; j += i) {signs[j] = 1;
            }
        }
    }
}

埃氏筛选法尽管看起来比拟快，但他也有本人的问题。首先他只能批量，对单个的 n 断定时也是须要筛出所有小于 n 的素数的。其次，它还须要依赖存储空间来存储标记。所以它依然无奈被用在超大素数的断定上。

有没有更快找到一个素数的办法？自从中世纪以来，有好多的数学家都在致力于寻找传中的素数公式。比方欧拉在 1772 年发现，$f(n) = n^2 + n + 41$ 当 n 小于 41 时 f(n)的值都是素数，尽管起初也有数学家相继发现了能生成更大素数的公式，但这些公式能生成的数仍旧是很无限的。到了高斯时代，基本上确认了简略的质数公式是不存在的，因而，高斯认为对素性断定是一个相当艰难的问题。

然而，事件总是有转折的。让咱们一起回到 1636 年，驰名数学家费马在一封信中写出这样一个公式。

如果 p 是一个素数，且 a 不是 p 的倍数，则有 a^(p-1) ≡ 1(mod p)

起初证实 a 不是 p 的倍数这个条件不是必须的。这个定理的含意就是只有 p 是素数，那么 $(a^(p-1))mod p$ 恒等于 1，这就是驰名的费马小定理。可能你曾经在想，能不能用这个定理来断定素数，的确 费马小定理反过来也简直是成立的 ，如果一个数 p 能使得 a^(p-1) ≡ 1(mod p)，p 有很大概率是个素数， 留神这里是简直成立。

public class PrimeNumCheck {public static boolean check(long a, long p) {long res = fastMod(a, p-1, p);
        return res == 1;
    }

    public static long fastMod(long x, long n, long m) {if (n == 1) {return x % m;}
        long tmp = fastMod(x, n>>1, m);
        if (n % 2 == 0) {return (tmp * tmp) % m;
        } else {return (tmp * tmp * x) % m;
        }
    }
    
    public static void main(String[] args) {System.out.println(check(2, 7));
    }
}

用如上 Java 代码，能够疾速的概率性断定一个数是否是素数（断定后果不是 100% 精确），这也取决于上述代码中 a 的抉择。下面用到了疾速幂算法，能将对一个数的 n 次幂取模的工夫复杂度降到 O(logn)。咱们仿佛能够将素数的断定工夫复杂度从 O(n)升高到 O(logn)，这是质的飞跃，从原来的简直不可计算变为可计算，这才为大素数的利用铺平了路线。

然而别急，它还有些小缺点。我刚说了费马小定理反过来是简直成立的，我始终在强调简直二字。因为有些和数 n 也能使得 $a^(n-1) ≡ 1(mod n)$ 成立，这些使得 $a^(n-1) ≡ 1(mod n)$ 的合数被称为基于 a 伪素数，比方前几个基于 2 的伪素数别离是 341、561、645……。不过这种伪素数也非常少，实际上，对于一个 512 位的数，其中基于 2 的伪素数不到 1 /10^20，如果是 1024 位的数的话，伪素数概率就只有不到 1 /10^41 了。这个概率到底有多低，举个例子，你能随机找到一个 512 位基于 2 的伪素数的概率比你中五百万大奖的概率都小。所以你是随机找一个素数，基于 2 的费马小定理断定曾经足够用了。

当然如果你非要谋求更高准确率的话，还是能够优化的，毕竟基于 2 的伪素数并不一定是基于其余 a 的伪素数，所以咱们 能够多换几个不同的 a 来进一步晋升上述代码的准确性。 但历史通知咱们凡事总有意外。有些合数对于任意的 a 都能使得费马定理成立，这些数被称为卡迈克尔数(Carmichael Number)，前几个卡迈克尔数别离是 561 1105 1729…… 对于卡迈克尔数又是另一个故事了。

费马小定理这种概率性的解法给了咱们解决问题的一种新思路，就好比用布隆过滤器一样，它们都不是百分百精确，但能够在准确性可控的状况下失去更高效的解决方案。计算机的世界不仅能够用空间换工夫，还能够用准确率换工夫。

像费马定理这种神奇的数学定理，我感觉这仿佛是上帝在造物时埋下的一个对于数字的小彩蛋，而我也深信这种小彩蛋还有很多，没准那天咱们能够发现上帝暗藏在圆周率里的笑话呢！！

维基百科素数测试
维基百科埃氏筛选 Sieve of Eratosthenes
维基百科卡迈克尔数
《算法导论》第 31 章素数测试

关于java:素数判定-高级程序员才知道的那些事儿

暴力试除

筛选法

费马小定理

小结

参考资料