素数算法

素数算法 数学家为何对素数着迷，素数规律如何关系着人类的信息安全？

素数的定义。

如果一个数只能被1和它本身整除，那么这个数叫做素数（1除外）。

至于1为什么不是素数，我在之前的一篇文章中已经做了回答。

素数的判断方法。

有一种方法叫做筛法。

这个筛怎么理解，我们可以把它理解成筛子。

筛子大家都见过吧，所有的数在筛子中一过，合数都漏下去了，筛子中剩下的数就是素数。

下面我为大家演示一下什么叫做筛法？从最简单的情况开始，已知第一个素数是2；2+1等于3，我们把3叫做2的后继数。

3不能被2整除，所以3也是素数，于是我们就得到了两个素数2和3；3的后继数是4，很显然4能被2整除，所以4是个合数；4的后继数是5，5不能被2整除，也不能被3整除，所以5也是一个素数。

只要后继数能被之前发现的任意一个素数整除，它就不是素数；不能被之前发现的所有素数整除，那么它才是一个新的素数。

我们将这个新的素数添加到素数表中，然后继续进行下去。

仅凭观察很难看出一个比较大的数是素数还是合数，比如101、401、601、701，都是素数，但301和901却不是素数，因为301等于7×43、901等于17×53。

这两个数冷眼一看，很像是素数，我列竖式算了好一阵儿，终于给分解出来了。

数学家并不满足用筛法去寻找素数，因为用筛法，带有一定的盲目性，并且随着数的增大，计算量也会越来越大。

数学家，一直渴望找出素数的分布规律，以便更好的掌握素数。

素数的分布情况。

1到1000之间有168个素数。

1000到2000之间，有135个素数。

2000到3000之间有127个素数。

3000到4000之间有120个素数。

4000到5000之间有119个素数。

随着自然数的变大，素数越来越稀疏。

至今数学家也没有找到素数分布的确切规律。

虽然素素越来越稀疏，但早在古希腊时代，欧几里得在几何原本中就已经证明了素数有无穷多个。

关于素数，有好多的猜想没有解决。

一、哥德巴赫猜想，任意一个充分大的偶数，都可以表示成两个素数之和。

二、梅森素数是否有无穷多个？如果能证明梅森素数有无穷多个，自然也就证明了有无穷多个完全数。

三、孪生素数，是不是有无穷多个？什么叫孪生素数？3和5，5和7，11和13，17和19，类似这样相差为2的一对素数叫孪生素数。

从孪生素数又引申到三生素数，如果三个素数甲、乙、丙，乙比甲多2，而丙又比乙多4，这样的三个数叫做三生素数。

比如5、7和11，11，13和17。

三生素数是不是有无穷多个，也是一个未解之谜。

与素数有关的好多问题都没有解决，这也是数学家着迷于素数的一个原因。

如果人们进一步发现了素数的分布规律，这些问题或许有望得到解决。

素数与现代密码学的关系。

现代密码学的原理是非对称加密，大家都知道密钥这个词。

对称加密算法中，加密和解密的密钥是一样的，面临的密钥分发的难题，一旦密钥泄露，密码很容易被破解。

非对称加密的密钥分公钥和私钥，其中公钥是公开的，谁都可以用公钥对信息进行加密，但知道公钥却不能解密，解密需要私钥。

有一种方法叫RSA算法，原理就是两个素数（比较大的）相乘求积很容易，已知其积分解素因数却非常难。

即便使用计算机也需要好几年，并且密钥还会定期更换，这样最大限度的保障了信息的安全。

在数学中，质数（也可以叫素数）是指那些只能被1和自身整除的自然数（大于1），例如，2、19、61、193，这些数只能被分解为自身与1相乘，除此之外，没有其他两个数相乘会得到这个数。

显然，任意两个质数的乘积是一个合数，只要知道任意两个质数，把它们相乘很容易就能得到结果。

然而，如果把一个由两个质数相乘得到的合数分解为两个质数却不是一件容易的事情，尤其是当这个数特别大的时候。

举个例子，38很容易可以质因数分解为两个质数——2和19，而要把11773质因数分解为两个质数——61和193难度就更大了，但如果要把68100029质因数分解为两个质数6899和9871更为困难。

随着质数的增大，把一个大数进行质因数分解的难度就会更大。

质数可以很大，人类现在找到的最大质数为2^77232917−1，这个质数的位数高达2325万位。

对于一个很大的数进行质因数分解极为困难，就连强大的超级计算机也很难算出来。

正是基于这样的特性，麻省理工学院的三位数学家发明了著名的RSA加密算法，这在商业加密中广泛应用，我们的yhk信息加密就是基于此方法。

简单来说这种原理如下：已知n是两个质数的乘积，m是需要加密的信息，那么，m^e除以n可以求出余数c，这个过程很容易。

但反过来，如果有人窃听到n、e和c，想要计算出m极为困难，除非窃听者可以把n质因数分解为两个质数。

但上面已经说过了，把一个很大的数质因数分解为两个质数非常困难。

在目前的RSA加密算法中，如果要破解这种加密算法，需要把位数达到309位的大数质因数分解为两个质数。

而如果未来这种加密算法继续升级，这种大数的位数可以达到617位。