在信息安全畛域，常常须要用到一些大素数，比方驰名的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章 素数测试