素数定理教学（数学思维系列你可能不知道）

大家在小学就学过素数了，素数也叫质数，就是除了1和自身之外没有其他约数(也叫因数) 的自然数，比如2、3、5、7、11等都是素数，而4、6、8、9就不是(这种数叫做合数)。回顾了素数的概念后，下面我们来聊聊与素数有关的有趣话题。

2是最小的素数，也是唯一的偶素数，2在所有素数中的地位和价值是非常独特的，我们已经在《你可能不知道的数字2》中进行了比较详细的介绍。

根据素数的定义和性质，任何一个自然数都可以分解为若干个素数的乘积。素数的个数是无限多的，欧几里得在《几何原本》中给出了一个非常经典的反证法证明，感兴趣的读者可以看参考文献1了解这个证明过程。素数有非常多有意思的性质和命题，有些命题比较简单，很容易证明，比如刚刚提到的素数个数是无限多的。有很多却非常困难，几百年以来，都没有被世界的数学家解决，这其中最出名的要数哥德巴赫猜想了。哥德巴赫猜想是说，任何大于等于4的偶数，都可以表示为两个素数之和。目前关于这一命题最好的结果是我国知名数学家陈景润的结论，陈景润证明了：一个充分大的偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合数。

上面是素数基础知识的介绍，看起来素数是数学家研究的话题，其实不然，素数与我们的生活密切相关，素数的如下3个性质是非常重要的。

1. 非常大的整数是难以分解为素因子的乘积的，需要非常大的计算量；
2. 素数没有1和本身之外的因子，素数和与它互质的数的最小公倍数是它们的乘积；
3. 素数在自然数中的分布是没有什么规律的；

下面我们来谈谈在自然界和人类生活中素数的价值，这些价值的发挥基本都与上面素数的3个特性有关。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成素数，以增加两个齿轮内两个相同的齿相遇啮合次数的最小公倍数(即是这两个齿轮齿数的乘积，两个素数的最小公倍数就是它们的乘积)，这可以防止有的齿经常和另一个齿轮的某一齿单一接触(特别是当这个齿设计有一些小的缺陷时，任何机械工程都是有一些小误差的)，可增强耐用度、减少故障。

图1：齿轮之间的咬合，如果每个齿轮是素数个齿，会更加安全耐用

上述齿轮齿数的设计其实是用到了素数与它互质的数的最小公倍数是它们的乘积这一性质，这一性质在生物学上也有比较有意思的现象。大家熟知的知了，学名叫做蝉，在自然界进化出了非常特别的繁殖周期，目前发现的有13年蝉、17年蝉等(读者可以看参考文献了解更多细节)，也就是它们的幼虫需要在地底下分别生活13年、17年才能破土而出，蝉出土后的生命一般只有2个月左右，为了绽放两个月的生命，它们需要在毫无光亮的地底下生活13年、17年，生命是多么的神奇和伟大啊！

13年蝉、17年蝉之所以进化出这种奇特的繁殖周期，是为了逃避天敌的侵害并安全延续种群，因而演化出一个漫长而隐秘的素数生命周期(13、17都是素数)。当蝉的繁殖周期是13、17年时，蝉与它的天敌繁殖周期碰到一起就需要经过它们繁殖周期的乘积这么多年，而如果他们的繁殖周期碰到一起的话，天敌的幼虫就会以蝉的幼虫为食，对蝉的种群延续是很不利的。蝉进化出这么奇怪的繁殖周期就是为了避免天敌的伤害，这里我们进一步看到了生物进化的魅力。

除了蝉以外，在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次使用的有效性也得到了科学的证明：实验表明，质数次数地使用杀虫剂是最合理的，并且需要在害虫繁殖的高潮期使用，这样害虫很难产生抗药性。这样使用主要是为了将相邻批次的繁殖期的害虫都被杀虫剂杀掉，避免了不同次代的害虫之间的交配繁殖。

在军事领域，以质数形式发出的无规律变化的导弹和鱼雷可以使敌人不易拦截，这是利用了素数分布的无规律性。

素数在我们日常生活中也非常有用，大家每个人都有很多账号和密码，素数与他们都有关系。素数与我们生活最相关的应用要数在密码学上的应用了。现在比较安全的密码很多都是基于素数理论构建的，它主要利用了将一个非常大的整数分解为素因子是一件非常困难的事情这一特性。基于素数构建的复杂密码体系，在有限的时间和现有的计算资源下基本是无法破解的。

我们知道，任何一个自然数都可以分解为素数的乘积，如果不计因数的次序，分解形式是唯一的。这叫做算术基本定理。但是将一个大整数分解却没有一个简单易用的好方法，只能用较小的素数一个一个去试除，耗时极大。如果用计算机来分解一个100位的数字，所花的时间要以万年计。可是将两个100位的数字相乘，对计算机却十分容易。美国数学家就利用了这一点发明了编制容易而破译难的密码体系，这种编码方式以三位发明者姓氏的首字母命名为RSA码。下面我们就来简单说明这种密码是怎么巧妙利用素数来构建的。

RSA密码的加密解密算法

下面讲解RSA密码的算法原理，我们可以通过如下8步来进行加密和解密，具体如下：

（1）选择一对不同的、足够大的素数p、q (p, q严加保密，不让任何人知道，p、q越大，也越难破解)；

（2）计算n=p*q；

（3）计算f(n)=(p-1)*(q-1) ；

（4）找一个与f(n)互质的数e，满足 1<e<f(n)；

（5）计算d，使得d*e ≡ 1 mod f(n)；

这里 ≡ 是数论中表示同余的符号。公式中 ≡ 符号的左边必须和符号右边同余，也就是两边模运算结果相同。显而易见，不管f(n)取什么值，符号右边1 mod f(n)的结果都等于1；符号的左边d与e的乘积取模运算后的结果也必须等于1。这就需要计算出d的值，让这个同余等式能够成立，一般可以通过逐个尝试的方法找到可行的d；

（6）公钥KU=(e, n)(公钥就是可以公开的，大家都可以知道)，私钥KR=(d,n)(私钥需要自己保密，用于破解密码用)；

（7）对于0至n-1之间的任意一个整数M，可以这样加密：C≡M^e(mod n)(这里M^e是指M的e次方，下面类似)，C就是需要传输的信息，将C给到你想传递信息的人；

（8）接收人收到信息C后，通过计算D=C^d(mod n)，就获得了原来的信息M，即D=M；

如果传输的信息很多，可以利用0、1、2、......、n-1 对信息进行编码(比如需要传输的是英文单词，可以对每一个字母编码，可以根据字母顺序编码，a->1、b->2、c->3、以此类推)。下面我们讲个例子让大家更好地理解上面的原理的正确性。对这个感兴趣的读者也可以自己尝试证明一下为什么这个密码体系是对的。

RSA密码的简单例子

令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3(3与20互质)，则e×d≡1 mod f(n)，即3×d≡1 mod 20，这时可以取d=7，满足e×d≡1 mod f(n)。这时公钥为：KU =(e,n)=(3,33)，私钥为：KR =(d, n)=(7,33)。

我们可以用这套密码体系来传输英文字母，用字母的顺序对应的数字来代表该字母。比如如果我们要传输字母y，可以这样进行：字母y在字母表中的序号是25，就用25来代替y，通过加密计算C≡M^e(mod n)≡25^3(mod 33) = 15625(mod 33)=16。你可以将16传给收信息的人，收信息的人收到16后，用D=C^d(mod n)来解密，具体计算是D=C^d(mod n) = 16 ^7(mod 33) = 268435456(mod 33) = 25，这就是y对应的序号，因此解密过程成功。

作者曾经设计的一个账号体系也用到了素数的知识，原理跟上面的RSA比较类似，大致意识是先确定账号的容量m ，即这个账号系统一共支持多少个账号，找一个素数p与m互质，找另个一个素数q，满足 p*q mod m =1(我的这个方法不要求p是素数，只要跟m互质就可以了，当然如果p是素数，只要不是m的因子，是一定满足跟m互质的条件的)。

我的这个方法设计非常精巧，也比较简单，它最大的价值是竞争对手通过注册几个账号是无法猜测出账号的生成规律的，从而无法知道你的产品有多少用户。下面我们来讲讲这个方法的具体实现原理。

每个用户根据他注册的次序给他赋予一个整数值k，即这个用户是第k个注册的，采用下面图2的算法获得该用户的账号(即后面的u1、u2、u3等等)。同时我们可以采用图3的算法根据用户的账号获得用户是第几个注册的用户。下面a的目的是为了让所有用户账号位数一样，比如如果a取9999999(9百99万9999)，m取90000000(9千万)，那么用户的账号范围就是10000000(1千万)到99999999(9999万9999)。大家可以看到这里面生成账号的过程类似RSA的加密过程，从账号获得用户注册顺序的过程类似RSA的解密过程。

图2：用户账号生成算法(类似于RSA的加密过程)

图3：从用户账号获得用户的序号(类似于RSA的解密过程)

素数在人类生活和自然界中的应用应该还非常多，等待聪明的人类来挖掘和探索。有兴趣的读者也可以结合素数的性质多思考，看是否能够找到素数的巧妙应用。

最后我们从一个新的角度来看待素数，如果对大学线性代数忘光的读者可以忽略下面的讲解。每个自然数n都可以表示为若干个素数的乘积(见下面公式，这里k是一共不同的素数个数，t_k是这个素数在n的因子中出现的次数)，如果将素数按照从小到大排序，这种表示是唯一的。

因此，素数在自然数中的价值有点像向量空间的基(向量空间中是加法，上式是乘法，本质是一样的，只要将上式两边取对数就变成了加法了)。如果把全体自然数想像成一个向量空间，素数就是这个空间的基，所有自然数都可以由素数全体组成的基底表示出来，只不过素数基底有无穷多个。任何一个自然数都可以看成由有限个基底张成的向量空间中的一个点。

参考文献

1. [百度百科关于素数的介绍] https://baike.baidu.com/item/质数/263515?fromtitle=素数&fromid=115069&fr=aladdin
2. [周期蝉] https://baike.baidu.com/item/周期蝉/2666050

,