不可思议的素数（下）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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，因为(p1)×(q1)=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 位数的大数字，所以不会太难)。

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

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

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

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

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

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

∑编辑 | Gemini

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

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

投稿邮箱：math_alg@163.com