不可思议的素数（下）

之前我们介绍了一个判断大数字n是否是素数的好方法，详见不可思议的素数（上）, 但是仅靠这个方法还远远不够。因为的展开会有(n+1)项，如果一一确认所有系数是否是n的倍数即分别用2,3,4…除以n的话，方法虽然简单却十分费时。不过，我们可以从中得到启发，然后发明一个高效的方法，现在来说明一下这个高效的方法。

5通过费马检测就是素数? 

17 世纪的数学家皮埃尔·德·费马发现了有关整数性质的各种定理和猜想。其中最有名的是“费马最后的定理”即“费马大定理”，内容为“当自然数n大于3时，关于自然数(x, y, z)的方程没有正整数解”。1995 年，安德鲁·怀尔斯在理查德·泰勒的帮助成功证明了“费马大定理”。费马拥有一本古希腊丢番图的著作《算术》，他随手在这本著作的边角空白处写下了这条定理。他还在书中留下了“我已经发现了如何证明这条定理，不过空白的地方太少不够写”等信息，这引来了外界的各种猜想。不过考虑到怀尔斯的证明方法，可以理解对于17 世纪的人们来说证明这个定理特别困难。

费马小定理的内容是“假如p 是素数，对任意自然数n，p 都能被 整除”。为了区分“费马大定理”，这条定理被称作“费马小定理”。同样，现在依然无法确认费马是否证明了这条定理。在第2 章“负数”一节中提到的莱布尼茨(他还会出现在第7 章的微积分中)最先发表了正式的证明过程。

例如假设p= 5，分别列出5 除以自然数n 的乘方得到的余数，即

n的值	12345
n  除以5的余数	12340
除以 5 的余数	14410
除以 5 的余数	13240
除以 5 的余数	11110
除以 5 的余数	12340

观察上述表格，可以发现“n 除以5 的余数”行和“除以5 的余数” 行中分布的数字完全一致。也就是说这两行的差等于0，所以5 能被整除，即费马小定理在p = 5 时是成立的。

那么，接下来我们用任意素数p 来证明费马小定理。首先来回顾一下，如果p是素数，那么用x的乘方展开时，p 能被展开式的系数整除。因此，假如n 是自然数，则是能整除p 的数。另一方面，费马小定理主张p 能被整除。总感觉这个和很像。

在研究数学或科学时，观察类似项经常能得到启发。中有，(n + 1)p − np − 1 中的np 带有一个负号。那么，如果将这两项相加，np 就相互抵消，即

仔细观察得到的算式，和之间存在某种关系。我们已经知道p能被中间的整除。所以“假设p能被整除”，那么p也能被整除。

也许你会疑惑“虽然得出了上述结论，但是我们不是要证明p 能被整除吗?为什么要假设原本就要证明的公式呢?”“如果对任意自然数n 费马小定理能够成立”，那么自然数(n + 1) 同样也能成立。不过，这也证明不了什么。于是，我们再回到最初的n = 1，那么，当然能将p 整除，因此费马小定理成立。因为刚才我们讲到“如果对任意自然数n 费马小定理能够成立”，那么自然数(n + 1) 同样也能成立，所以当n = 1 时费马小定理能够成立的话，那么n + 1 = 2 时同样也能成立。

重复上述公式，当n = 2 时费马小定理能够成立的话，那么n = 3 时同样也能成立。当然n = 4、n = 5 时都能成立。就像多米诺骨牌一样，从小数字的n 到大数字的n 依次证明费马小定理。

从“n 成立的话”⇒“(n + 1) 同样也成立”证明有关自然数的定理。这种类似多米诺骨牌的证明方法叫作“数学归纳法”。

那么，假如p 是合数，又会得到什么结果呢?例如假设p = 6, 计算56 −5除以6后的余数。除以6余1,5除以6余5，也就是说和5 除以6 的余数并不相等。因此6 无法被 整除。根据费马小定理，如果p 是素数，p 能被 整除，所以证明了6 不是素数。

我们当然知道6 不是素数，不过不管p 的值有多大，也能立刻计算出除以p 后的余数，所以只要余数不等于0，就能判断出p 是合数。这就叫作费马素性检验。如果无法通过费马素性检验，就说明不是素数。

刚才已经讲过，判断自然数p 是否为素数时，通过按顺序除以2、3 . . . 来验证是否能够整除的话，效率实在太低。如果p 多达300 位数，即使用京速计算机从宇宙诞生时计算到现在也没办法算出结果。于是，使用费马素性检验的话，可以大幅度地减少计算次数。

然而，费马检测并不完美。因为不能通过费马素性检验的是合数，

但是通过检验的也不一定是素数。例如561 = 3 × 11 × 17 是合数，对任意数n，561 能被整除。而且数学家已经证明了这种“伪素数”( 其实它有一个响亮的名字叫“ 卡米切尔数” ) 有无穷个。

在帕斯卡三角形中，如果p 能被第(p + 1) 行第一项和最后一项以外的数整除，那么可以判断p 是素数。虽然费马素性检验也采用了这个定理，但是判断基准稍显薄弱。2002 年，印度理工学院坎普尔分校的马尼德拉·阿格拉沃尔教授和他的两个学生尼拉基·卡雅尔、尼汀·萨克西纳成功对其进行了改良，发现了对于p位数N，通过计算次后，可以判断是否真为素数。甚至最近已经成功将计算次数减少次。例如p 约为，因为，所以用京速计算机的话只需0.1 秒即可完成计算。多亏阿格拉沃尔开发了运用素数性质的算法，瞬间解决了从宇宙诞生开始至今都无法完成的计算。

6保护通信秘密的“公钥密码” 

自然数，特别是素数的性质与密码通信的方法存在密切联系。按照一定规律将通信内容替换成其他符号的过程叫作加密，反之将加密的数据恢复成原来内容的过程叫作解密。1970 年以前所使用的密码只要掌握加密规则，就能解密。例如公元前1 世纪尤利乌斯·恺撒用过的密码，因为这个密码是让字母表中的文字按照一个固定数目进行偏移，所以只要从反方向移动相同数目的文字即可完成解密。因此，如果敌方获悉加密规则的话，也就泄露了通信秘密。例如记录加密规则的文件被盗或者敌方从通信模式中破解了加密规则。

1925 年到第二次世界大战期间，德国军队使用的密码机“恩尼格玛” (意为哑谜)通过复杂地组合齿轮来替换字母。而且，其构造保证每次使用的替换规则都不同，当这个密码机被认为不会被破译。但是，每天早晨严谨的德国士兵在加密并发送更换初始设置的方法时，总是发送两次消息，以免出现失误。波兰情报密码处的年轻数学家马里安·雷耶夫斯基发现德国士兵在每天早晨的通信中首先会重复发送两次消息，他运用了被称为群论的数学原理破解了这个消息模式，破解了齿轮的设置。1939 年德军进攻波兰时，自知无法保卫祖国的波兰情报密码处官员邀请英国和法国的情报将校来华沙，并告诉了他们有关“恩尼格玛”的秘密。后来英国的政府代码及加密学校(GC&CS, Government Code and Cipher School)以这个信息为基础，成功破解了德军的密码通信，为欧洲联盟的胜利作出了巨大的贡献。

一旦加密规则泄露，加密对象就有可能被解密，这是加密无法避免的问题。不过，这个问题存在解决方法。1976 年，美国的威特菲尔德·迪菲和马丁·赫尔曼最早提出解决方案。为了更好地解说他们的想法，首先我们试着联想一下挂锁。

挂锁扣入锁扣后，就固定住了。这谁都知道。一旦挂锁被锁上，除非是有钥匙的人或者具有开锁技能的人，否则就无法开锁。

即便懂得如何上锁，也不一定懂得如何开锁。上锁的知识对开锁没有任何帮助。

迪菲和赫尔曼一直在思考是否能够发明类似挂锁的密码。如果发明了即使掌握加密规则者也无法轻易解密的密码，那么就没有必要隐瞒加密规则了。对外公开加密规则，这样的话，所有人都能够掌握如何对通信内容加密。这就像世界上布满了挂锁，所有人都能随心所欲地发送被锁保护的信件。虽然锁被公开了，但是开锁的钥匙握在自己手中，只要保护好手中的钥匙，谁都无法在通信过程中打开受保护的加密信件。同样，即使公开加密规则，只要不公开解密规则，就能守住通信秘密，这就是迪菲和赫尔曼的想法。互联网通信中所使用的RSA 密码正是这种“公钥密码”想法的具体实践。

7公钥密码的钥匙，欧拉定理

在解释RSA 密码前，我们先来介绍欧拉定理。这个定理是费马小定理普遍化的产物。费马小定理的内容是假如p 是素数，对于任意数n，p 都能被整除。

在这个表中，n 除以5 的余数与除以5 的余数一致，这就是费马小定理。还有其他有趣的规律吗?观察“除以5 的余数”这行，除了最右边一项以外，其他都是1。因为最右边一项n 正好是5 的倍数，所以如果n 不是5 的倍数，那么除以5 的余数都是1。一般情况下，当p是素数时，如果n不是p的倍数，那么除以p的余数都是1。

上述公式可以从费马小定理中推导出来。虽然费马小定理主张p 能被整除，不过因为所以如果n 本身不是p 的倍数，也就是说p 不能被n 整除的话，p 应该能被整除。因此可以证明。这有时也被称为费马小定理。

18 世纪数学家欧拉扩展了费马小定理。费马小定理可以计算除以素数p 的余数，不过欧拉定理还考虑到n 除以一般自然数m 的余数。m 不一定是素数，不过除了1 以外，n 和m 没有共同的因子。也就是说，n 和m 的最大公约数是1。这个时候，n 和m 是“ 互素数”。与m 互质的自然数n 的数目记作φ(m)，例如当p 和q 是不同的素数时，φ(p) = p − 1φ(p × q) = (p − 1) × (q − 1) 这个函数φ(m) 也被叫作欧拉函数。欧拉定理主张，假如自然数n 与m 互质，那么例如m = p 是素数的话，因为φ(p)= p − 1，所以这也是费马小定理的内容。当m 是素数时，欧拉定理也是费马小定理。公钥密码使用了“ m 是两个素数p 和q 的乘积”，即m = p × q 。

当m = p × q 时，因为φ(p × q) = (p − 1) × (q − 1)，如果素数p 和q 不能被自然数n 整除，那么成立。例如假设给定两个素数p = 3, q = 5，那么m = p × q = 15，φ(3 × 5) = (3 − 1) × (5 − 1) = 8。如果n 与15 互质，那么假设n = 7，你可以试着代入公式。使用欧拉定理可以发现数字具有有趣的性质。例如因数分解类似9、99、999 等由9 构成的数字时，可以证明不包括2 和5 的所有素数会在某处出现。详情请参考我个人主页的补充知识。

下一节要说明使用欧拉定理的密码，现在先提前准备一下。根据欧拉定理，如果素数p 和q 不能被自然数n 整除，那么成立。即使进行s 次方，因为1s = 1，所以

再乘以n 的话，

也就是说，对于任意数n，只要素数p 和q 无法被整除，除以p × q 的余数依然等于n。

那么，接下来将上述结果运用于公钥密码。

8信用卡卡号SSL 传输的原理

密码技术常用于网购、管理银行账号以及居民基本登记册等方面。对网络信息加密传输叫作SSL(Secure Sockets Layer)。在Web 浏览器输入https://www....的话，就是通过SSL 发送或接受信息。

只要使用公钥密码，任何人都能对信用卡卡号等个人信息进行加密处理，并且在网络上发送加密的信息。但是，只有掌握了解密规则的接收者才能解读信息。

因为是罗纳德·李维斯特、阿迪·萨莫尔和伦纳德·阿德曼开发了RSA 密码，所以其命名RSA 就是由他们三人姓氏的首字母组合而成A。

RSA 密码的步骤如下: (1)密码的接收者，假设是亚马逊网站(Amazon.com)，为了设置公钥密码，选出2 个数值较大的素数，记作p 和q。(2)亚马逊网站再选一个自然数k，为(p − 1) × (q − 1) 的互素数。

例如，假如p=3, q=5，因为(p−1)×(q−1)=8，所以选择8的互素数，例如k = 3。

(3)亚马逊网站计算m = p × q，然后告诉你m 和k 的值。这就是公钥密码。不过，亚马逊网站不会告诉你m 的质因数p 和q 分别是多少，只会告诉你这两个素数的乘积。假设代入刚才的例子，那么m = p × q = 15。因为15 这个数字太小，我们很容易推算出15 的质因数是3 和5。但是，RSA 密码使用的数差不多有300 位数，所以不可能分解质因数。

(4)你将信用卡卡号等想要发送的信息替换成自然数n。不过n 必须小于m，而且n 和m 必须是互素数(因为m 是有300 位数的大数字，所以不会太难)。

(5)你使用从亚马逊网站接收的密钥信息(m, k)，对n 进行加密处理。加密规则是计算，再用除以m 得到余数。将计算结果记作α，即

将α 作为密码，通过网络向亚马逊网站发送信息。例如，n=7，那么计算73 除以15得到余数。因为，所以α = 13。(6)亚马逊网站收到密码α 后，对n 进行解密，恢复成原来的信息。步骤(6)是RSA 密码最关键的部分。亚马逊网站必须解决“有一个未知数n，当除以m 得到的余数是α 时，n 等于几?”的问题。如果少了“计算除以m 得到余数”这一步骤，答案的计算就非常简单。如果=α的话，那么只要求出α的k次方即可。

求普通数的k 次方时，可以不断靠近正确答案。例如想要知道= 343 中n 等于几，首先我们随便推测一个数n = 5，计算得出= 125，所以推测的n 会大于5。那么加大数值推测n = 9，计算得出= 729，推测的n 又太大了。n 的数值变大，也会随之大，所以n = 5 太小n = 9 又太大的话，正确答案就是介于两者之间。经过多次计算，最终会得到正确答案n = 7。

然而，如果增加“除以15，计算得到的余数”这一步骤，问题就变得麻烦了。因为除以15 得到余数的话，15 除以15 余数就变成0，所以不管n 变得多大，除以15 得到的余数却不一定会变大。实际上，对于15的互素数n=1, 2, 4, 7, 8, 11, 13, 14，除以15得到的余数等于1, 8, 4, 13, 2, 11, 7, 14，看不出来数字排列中是否存在什么简单的规律。所以，即使知道“除以15 得到的余数”，也很难计算出n 的值。如果是类似15 的小数，倒是可以一一验算，但是如果是300 位数，也只能束手无策。

不过，亚马逊网站却能简单地解决这个问题。因为已知m 是p × q 的乘积，根据这个信息，就能判断出“幻数”r。r 是破解密码的关键。有一个未知数n，而且知道那么使用幻数r 的话，

也就是说，可以从密码α 中还原原来的数n。例如当公钥密码的m=15, k=3时，因为，所以对7 加密后α = 13。然后你把这个信息发送个亚马逊网站。此时，幻数r = 3。亚马逊网站知道r = 3，并在收到密码13 后，计算其3 次方即。因为对密码13进行3次方后再除以15得到的余数是7，所以可以将加密的信息还原成加密前的信息即n = 7。

亚马逊网站是如何发现幻数r 的呢? α 原本是用来计算 所以代入幻数r 后，得到也就等于

我们再回想一下欧拉定理，如果p 或q 能被n 整除的话，那么

这两个公式非常相似。两者都是计算n 的乘法，最终又回归到n。因此，如果能够准确选择r，得到r × k = 1 + s × (p − 1) × (q − 1) 的话，密码自然迎刃而解。

在这个过程中，最重要的是k 与(p − 1) × (q − 1) 是互素数。此时，r × k = 1 + s ×(p − 1) × (q − 1) 

中的自然数r 和s 肯定存在。例如在刚才的例子中，k =3，(p − 1) × (q − 1) = 8，因为这两个数是互素数，所以假设r = 3，s = 1，那么如果用公式 计算密码α，那么代入r，即可得出

于是从α 中求出n，即成功解密。公式中的r 就是亚马逊网站的幻数。大数的分解质因素越复杂，就几乎无法破解RSA 密码。在现在已知的算法中，对N 位数的自然数进行分解质因数需要花费的时间，相当于解关于N 的指数函数。例如在2009 年某个团队成功对232 位的数进行了分解质因数，不过整个过程使用了几百台行处理计算机，而且历时长达2 年。如果能够发明一种算法缩短计算时间，比如耗时相当于计算N 的乘方的话，仅靠使用公钥密码的RSA 密码马上就会被破解，从而导致互联网经济陷入一片混乱。

其实理论上存在破解方法，不过暂时还没有实现。众所周知，如果人们成功制造运用量子力学原理的“量子计算机”，对N 位数的自然数进行分解质因数所需的时间就缩短至计算N 的乘法。因为1994 年麻省理工学院的数学家彼得·秀尔通过对N 位数的自然数进行了次的计算后，发现了分解质因数的算法。不过，“量子计算机”还处在理论摸索阶段，尚未进入实践环节。

另一方面，使用量子力学的原理还有可能发明另一种异于RSA 密码的密码通信。如果使用“量子密码”，一旦中途出现密码被盗的情况，即使盗密者躲起来偷偷解读，也绝对会被发现。只要量子力学正确，就绝对不可能被窃密。一旦“量子计算机”和“量子密码”中的任何一个技术成功问世，通信安全领域又会迎来巨大的变革。

1995 年人类终于成功证明了近4 世纪都未曾解决的费马大定理，2003 年对于双子素数的证明又向前发展了一大步。而且，1997 年运用了欧拉定理的RSA 密码问世，2002 年又发明了高效的素数检测法。自数学诞生起，人类用了几千年时间研究自然数，而且直至今日还在不断分析其性质、开发其应用，仍然还存在无数的未解之谜。

19 世纪的美国思想家和诗人亨利·戴维·梭罗曾经说过:“数学是诗，不过大部分还尚未被人诵读。”关于素数，想必以后还会有更多的诗为人诵读吧!欧拉定理被运用在RSA 密码中，从而实现了互联网结算。有关素数的新发现也许会给我们今后的生活带来巨大的变化。

本文来源《用数学的语言看世界》，本书由人民邮电出版社图灵新知出版。

∑编辑 | Gemini

算法数学之美微信公众号欢迎赐稿

稿件涉及数学、物理、算法、计算机、编程等相关领域，经采用我们将奉上稿酬。

投稿邮箱：math_alg@163.com

总结

以上是生活随笔为你收集整理的不可思议的素数（下）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。