素数判定高级程序员才知道的那些事儿

刺骨的言语ヽ痛彻心扉 2021-09-25 08:40 328阅读 0赞

在信息安全领域，经常需要用到一些大素数，比如著名的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)`的时间复杂度。

![在这里插入图片描述][d9ebca42efa91fa37c9281882f41cdf9.gif_pic_center]  
其原理是这样的，设置一个标记数组，开始先把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 f(n) = n^2 + n + 41 f(n)=n2\+n\+41 当n小于41时 f(n)的值都是素数，虽然后来也有数学家相继发现了能生成更大素数的公式，但这些公式能生成的数依旧是很有限的。到了高斯时代，基本上确认了简单的质数公式是不存在的，因此，高斯认为对素性判定是一个相当困难的问题。

## 费马小定理 ##

![https://img-blog.csdnimg.cn/2021050914550158.png\#pic\_center][https_img-blog.csdnimg.cn_2021050914550158.png_pic_center]  
然而，事情总是有转机的。让我们一起回到1636年，著名数学家费马在一封信中写出这样一个公式。

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

后来证明a不是p的倍数这个条件不是必须的。 这个定理的含义就是只要p是素数，那么 ( a ( p − 1 ) ) m o d p (a^(p-1))mod p (a(p−1))modp恒等于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 ( m o d n ) a^(n-1) ≡ 1(mod n) a(n−1)≡1(modn)成立，这些使得 a ( n − 1 ) ≡ 1 ( m o d n ) a^(n-1) ≡ 1(mod n) a(n−1)≡1(modn)的合数被称为基于a伪素数，比如前几个基于2的伪素数分别是341、561、645……。不过这种伪素数也非常少，实际上，\*\*对于一个512位的数，其中基于2的伪素数不到1/1020\*\*，如果是1024位的数的话，伪素数概率就只有不到1/1041了。这个概率究竟有多低，举个例子，你能随机找到一个512位基于2的伪素数的概率比你中五百万大奖的概率都小。 所以你是随机找一个素数，基于2的费马小定理判定已经足够用了。

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

## 小结 ##

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

像费马定理这种神奇的数学定理，我感觉这似乎是上帝在造物时埋下的一个关于数字的小彩蛋，而我也坚信这种小彩蛋还有很多，没准那天我们可以发现上帝隐藏在圆周率里的笑话呢！！

## 参考资料 ##

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

[d9ebca42efa91fa37c9281882f41cdf9.gif_pic_center]: /images/20210923/defd5fbeb7584bfe9253e00eacb870bb.png
[https_img-blog.csdnimg.cn_2021050914550158.png_pic_center]: /images/20210923/5fca5aaf57d84f2784681ae37a78064a.png
[Link 1]: https://en.wikipedia.org/wiki/Primality_test
[_ Sieve of Eratosthenes]: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
[Link 2]: https://en.wikipedia.org/wiki/Carmichael_number