关于本书

《质数了不起——知乎刘巍然作品》/刘巍然

主办方 知乎网（www.zhihu.com）
出品人 周源
策划编辑 梅莹 刘强
营销编辑 胡晓曦
实习编辑 裴启航
设计 刘奕含
校对 高正哲

联系我们 publish@zhihu.com

本电子书版权为北京智者天下科技有限公司所有，未经书面授权，不得在任何地区以任何方式反编译或节录本书内容。

ZHI-BN:8-0047-0000160816-1
DNA-BN：ECFD-N00007373-20160322
最后修订：2016 年 8 月 18 日

出版：浙江出版集团数字传媒有限公司
浙江 杭州 体育场路 347 号
互联网出版许可证：新出网证（浙）字 10 号
电子邮箱：cb@bookdna.cn
网　　址：www.bookdna.cn
BookDNA是浙江出版联合集团旗下电子书出版机构，为作者提供电子书出版服务。
如您发现本书内容错讹，敬请指正，以便新版修订。

Zhejiang Publishing United Group Media CO.,LTD,2016
No.347 Tiyuchang Road, Hangzhou 310006 P.R.C.
cb@bookdna.cn
www.bookdna.cn

「一小时」电子书出版序

知乎创始人 周源

感谢你阅读知乎推出的「一小时」系列电子书。

「一小时」系列是什么？

这是一系列短小精炼的电子书。我们邀请了知乎各专业领域的知友在书中分享他们的知识、经验和见解。如果你足够认真，便可以在一个小时内读完一本书。

这里既有日常经济分析，也有人文历史，既有职场经验，也有生活中的科学。这些作者，都是我们精心为你寻找，在各个领域拥有独到见解的专业人士。而我们出版的每一本书，都会解释一个问题，分享一种思路，展开一个视角。

地铁上，入睡前，在这些细碎的时间里，你可以挤出一小时的时间，静下心，读下去。

你很忙，但知识不慌张。

愿你从「一小时」开始，对这个世界，又多了一分认识。

作者序

在小学五年级接触除法运算时，我们便学习了质数和合数的概念。不过，很多人可能会好奇：为什么在中学甚至大学后我们就很少再接触质数相关的进一步理论和应用了呢？近年来，质数相关的重量级研究成果与奖项频出，这更是激发了人们对质数的好奇心。2013 年，华人数学家张益唐对数论中的著名猜想「孪生素数猜想」做出了突出贡献，相关成果已被数学领域顶级期刊《数学年刊》接收[1]。2015 年，前 Sun Microsystems 公司的首席安全官 Whitfield Diffie 和斯坦福大学电气工程系名誉教授 Martin Hellman，因在现代密码学领域的重要贡献而获得计算机科学界的最高荣誉ACM图灵奖[2]，而他们的贡献和质数息息相关[3]。质数到底具有何种性质，这一如此简单的数学概念为何一直散发着无穷的魅力呢？

质数的研究涉及到数学中的一大分支：「数论」。这是一个纯粹的数学分支，主要研究整数的性质。之所以称数论是一个纯粹的数学分支，正是因为这一分支在很长时间以来仅涉及数学理论，难以在实际中找到特定的应用。然而，随着现代密码学这一新兴学科在 1970 年代的建立和发展，数论终于在应用层面找到了归宿。现今，数论的相关研究成果被广泛应用于密码学中，成为计算机网络安全通信、安全存储、身份认证等安全机制的核心理论基础。

我很希望借助这样一个机会为普通读者普及质数的相关知识。在这本书中，我们将沿着历史的踪迹，首先概览那些与质数相关的知识。随后，我们穿越历史的长河，回到 1970 年代，讲解现代密码学的诞生，以及现代密码学与质数千丝万缕的联系。最后，我们畅想未来，简单聊聊密码学的发展方向。我希望我的粗浅讲解能让越来越多的朋友们了解日常生活中所使用的密码和安全机制，并以此为契机，独立自主地掌握互联网中保护个人隐私的常用方法。同时，如果有人能因我的讲解而喜欢上密码学与信息安全，愿意在未来投身于信息安全事业，那就更好啦。

作为一个主修公钥密码学的博士研究生，我几乎每天都和看似简单却又魅力无穷的质数打交道。然而，谈谈质数本身对我来说是一个充满挑战性的任务。首先，人类对于质数的研究横跨了数学的整个探索历史。因此，质数的讲解需要我查阅历史，把握质数研究和发展历程的脉络。其次，谈到数学和密码学就不可避免地涉及较多的定理与性质。如何通俗易懂地讲解这些性质，对任何一位作者来说都是一项充满挑战性的工作。本书中，我试着向读者们呈现质数相关的神奇性质，同时规避较难理解的数学概念、定义和定理，并进一步为大家讲解质数如何默默地在背后保护着我们的数据安全。

虽然我已经尽我所能全力确保本书的正确性和严谨性，但由于受我个人的知识面有限，书中的错误和不当之处在所难免，恳请广大读者提出宝贵的意见和建议。

另外，本电子书的数论基础知识介绍部分参考了《离散数学及其应用（原书第五版）》[4]、《信息安全数学基础》[5]、《网络安全——技术与实践（第 2 版）》[6]中的相关内容。部分密码学的发展历史参考了《密码的奥秘》[7]中的相关内容。非常感谢。

质数了不起

质数的定义：整数之间的整除关系

最简单的运算：加减乘除

最开始的内容总是最轻松的内容，那我们干脆来个最轻松的。我们一口气回到上古时代，回顾一下数字的发展历史吧！人类为什么会引入数字呢？其实本质上就是为了运算。人类每多理解一个运算，就会对应地多了一些符号和一些数字。

最早出现的数字是「自然数」。自然数之所以叫自然数，是因为很早以前我们就会数数了。小孩子自然就知道有 1 个苹果、2 个香蕉。去掉苹果和香蕉，剩下的 1 和 2 就是最早的数学。

有了自然数，人类就可以愉快地做「加法」了。1 个苹果加上 1 个苹果等于 2 个苹果（1+1=2），3 个香蕉加上 5 个香蕉等于 8 个香蕉（3+5=8），加法的引入非常轻松。

有了加法，自然而然也就有了「减法」。大的数与小的数相减不会遇到什么问题。我有 3 个苹果，给了你 1 个苹果，我还有 2 个苹果（3−1=2）。但是，小的数与大的数相减就麻烦了。昨天我有 3 个苹果，今天我还有 3 个苹果，苹果数量没有变化。没有变化用什么数字表示呢？为此，人类引入了 0 的概念。更严重的问题是，昨天我有 3 个苹果，今天我只有 2 个苹果，苹果数量少了 1 个。少了 1 个用什么数字表示呢？为此，人类引入了「负数」的概念。人类规定，小于 0 的数是「负数」，大于 0 的数则为「正数」。这样，我们就可以解决少了 1 个的表示问题，顺利执行减法运算了（2−3=−1）。有了自然数、0、负数、加法和减法，人类已经基本解决了计数问题。

为什么负数这么好用呢？我们实际上也可以这么理解负数：负数是与某个正数相加后结果为 0 的数。如果给定的整数是 a，我们就把与 a 相加等于 0 的数表示成−a。这样一来，2−3 就可以写成 2+(−3)了。只要定义了负数，我们就可以把减法也用加法来表示。后面我们会使用这个概念来理解负数和减法。

再往后，人类发现加法和减法还是不够：古代战争时士兵总站成方阵的形式，5 行7 列什么的。此时，用什么方法可以快速得到方阵中的士兵总人数呢？为了解决这个问题，人类引入了「乘法」的概念。通过乘法运算，我们很快就能知道 5 行 7 列一共有 35 个士兵（5×7=35）。有了乘法，自然就出现了「除法」：一共有 35 个士兵，站成 7 列，应该有多少行呢？运用除法，我们可以快速得到应该有 5 行（35÷7=5）。

然而，除法的概念并不是想象的那么简单，因为有除不尽的情况。我们称两个数相除的结果为「商」。如果除得尽，商就是个整数，我们前面提到的 35÷7=5 结果就是整数。再比如 12÷3=4，结果也是整数。然而，如果除不尽，结果就不是整数了。比如 11÷4，结果不能用自然数、0 或者负数表示结果。为了解决这个问题，人类想了两个办法。第一个方法是引入「余数」的概念：如果除不尽，就把除不尽的部分剩下来。比如 11÷4 的商为 2，余数为 3，这样就巧妙地解决了除不尽的问题。第二个方法是引入「小数」和「分数」的概念，也就是再用一种新的形式来表示结果。比如 11÷4==2.75，就把结果分别用分数和小数来表示了。我们知道，如果用小数表示除不尽的结果，还会出现两种情况：得到的结果是有限小数，比如 11÷4=2.75；得到的结果是无限循环小数，比如 2÷3=0.6666…。但如果用分数表示除不尽的结果就不会带来这样的麻烦。

为什么分数这么好用呢？我们把分数分开看：分数包含「分子」和「分母」。和减法与负数的概念类似，我们可以把分数看成分子和分母的「倒数」相乘的形式：=11× 。我们把倒数理解成：与某个整数相乘结果等于 1 的数。如果给定的整数是 a，我们就把与 a 的倒数表示成 a −1 。例如，由于 4× =1，我们可以把写为 4⁻¹，这样，就写为 11× =11× 4⁻¹。只要定义倒数，我们就可以把除法也用乘法来表示。后面我们会使用这个概念来理解倒数和除法。

至此，人类已经愉快地定义了自然数、0、负数、分数等最为基本的概念，以及加法、减法、乘法、除法等最为基本的运算。直到「第一次数学危机」之前，人类的数学一直和平有序。而我们要讨论的运算也就到此为止。我们甚至都不会涉及到分数，仅考虑整数的问题。

质数的定义与哥德巴赫猜想

引入余数和引入分数造就了不同的数学路线。在小学时，我们走向了引入分数的路线。引入分数的结果是在初中引入了「无理数」，在大学引入了「实数」，最终走到了「高等数学」领域。于是，人们想起了被数学支配的恐惧。那么另一条路线怎么样呢？我们这次就走一走另一条路线，看看会发生什么。

回到除法运算上面。如果整数 b 除以整数 a 后还能得到一个整数 c，我们就称 a「整除」b，且称 a 是 b 的一个「因子」，b 是 a 的「倍数」。例如，12÷3=4 是整数，我们称 3 整除 12，3 是 12 的因子，12 是 3 的倍数。

有了整除和因子，我们就可以回顾「质数」的概念了。大于 1 的每一个正整数都至少能被两个整数整除，因为它们都可以被 1 和它自己整除。如果一个正整数只能被 1 和它自己整除，即一个正整数只有 1 和它自己两个正因子，我们就称这个整数为质数（或为素数）；否则，我们称这个整数为「合数」。例如，1 和 7 是正整数 7 仅有的正因子，因此 7 是质数。正整数 9 拥有 3 个正因子 1、3、9，因此 9 是合数。

有了质数和合数的概念，我们惊讶地发现竟然可以讲解数学历史上最为著名的一个猜想：「哥德巴赫猜想」[8]了。

1742 年 6 月 7 日，普鲁士数学家哥德巴赫（Christian Goldbach）给瑞士数学家欧拉（Leonhard Euler）写了一封信，在信中提出了以下的猜想[9]：

任意一个大于 5 的整数都可以写成三个质数的和。

三周后，欧拉在 6 月 30 日向哥德巴赫撰写回信，并在回信中注明此猜想有另一个等价论述：

任意一个大于 2 的偶数都可以写成两个质数的和。

欧拉在回信中同时指出[10]：

然而，任意数字都可以由两个质数组成，我非常确信这是一个定理，尽管我无法证明。（i）

现今我们了解到的哥德巴赫猜想论述为欧拉给出的版本，亦成为「强哥德巴赫猜想」。从强哥德巴赫猜想还可以推出一个稍弱的假设：

任意一个大于 5 的奇数都可以写成三个质数的和。

这一论述称为「弱哥德巴赫猜想」。已经证明，如果强哥德巴赫猜想是正确的，那么弱哥德巴赫猜想一定也是正确的[11]。

图 1：哥德巴赫信件手稿影音本第 127 页描述了哥德巴赫猜想

哥德巴赫猜想的论述如此简单，几乎每一个学习过一点数学的朋友都可以理解猜想的内容。然而，哥德巴赫猜想的证明却又如此的困难。至今为止，强哥德巴赫猜想依然没有得到证明，也没有找到反例；弱哥德巴赫猜想的证明取得了突破进展，2013 年，弱哥德巴赫猜想基本得到了完全证明[12]。

实际上，从 1742 年哥德巴赫正式提出了这个猜想，到 1920 年代之前，哥德巴赫猜想的证明没有取得任何实质性的进展。1900 年，德国数学家希尔伯特（David Hilbert）在巴黎举行的第二届国际数学家大会上作了题为《数学问题》的演讲，并提出了 23 道最为重要的数学问题[13]。其中，第八个问题就包括了哥德巴赫猜想和与它相似的「孪生质数猜想」（稍后我们就会见到孪生质数猜想了）。实际上，至今除了包括哥德巴赫猜想在内的 4 个问题外，其它的 19 个问题都得到了解决或者部分解决。

十九世纪至二十世纪初，欧洲数学家们在「数论」与「函数论」方面取得了辉煌成就，为哥德巴赫猜想的突破提供了坚实的数学基础。

数学研究的一般都不是一蹴而就的，而是由易到难，先证明一个简单，甚至条件有点苛刻的结果。然后，通过优化证明中使用的技巧，或者加入新的技巧，从而逐渐接近最终的目标。哥德巴赫猜想的研究就是如此。1920 年左右，英国数学家哈代（Godfrey Harold Hardy）和利特尓伍德（John Edensor Littlewood）极大地发展了解析数论，建立起「圆法」工具，并用圆法证明了：如果「广义黎曼猜想」（Generalized Riemann Hypothesis）成立，则每个充分大的奇数都能表示为三个质数的和；「几乎」每一个充分大的偶数都能表示成两个质数的和。注意这里的「几乎」和「充分大」，哈代和利特尓伍德依赖了另一个猜想，经过了艰苦的努力，也还没证明出「每一个」。但他们的工作对哥德巴赫猜想的证明做出了巨大的贡献。1997 年，法国数学家 Deshouillers 及其合作者 Effinger、Te Riele 和 Zinoviev 证明，在广义黎曼假设猜想成立的前提下，弱哥德巴赫猜想是完全成立的[14]。Kaniecki 证明，在广义黎曼假设猜想成立的前提下，奇数都可以表示为最多五个质数的和[15]。2012 年，华人数学家陶哲轩在无需广义黎曼假设猜想的情形下证明了这一结论[16]。

序号

问题名称

进展

01

连续统假设

部分解决

02

算术公理之相容性

已解决

03

两四面体有相同体积之证明法

已解决

04

建立所有度量空间使得所有线段为测地线

论述晦涩，无法解决

05

所有连续群是否皆为可微群

已解决

06

公理化物理

非数学问题

07

若 b 是无理数、a 是非 0、1 代数数，

那么 ab 是否超越数

已解决

08

黎曼猜想、哥德巴赫猜想、孪生素数猜想

未解决

09

任意代数数域的一般互反律

部分解决

10

不定方程可解性

已解决

11

代数系数之二次形式

已解决

12

一般代数数域的阿贝尔扩张

未解决

13

以二元函数解任意七次方程

已解决

14

证明一些函数完全系统的有限性

已解决

15

舒伯特演算之严格基础

部分解决

16

代数曲线及表面之拓扑结构

未解决

17

把有理函数写成平方和分式

已解决

18

非正多面体能否密铺空间、球体最紧密的排列

已解决

19

拉格朗日系统之解是否均可解析

已解决

20

所有有边界条件的变分问题是否都有解

已解决

21

证明有线性微分方程有给定的单值群

已解决

22

将解析关系以自守函数一致化

已解决

23

变分法的长远发展

未解决

表 1：希尔伯特 23 个问题的解决进度

另一方面，在哈代和利特尓伍德建立圆法工具的前 1 年，也就是 1919 年，挪威数学家布朗（Viggo Brun）推广了公元前 250 年就出现在古希腊的「筛法」，并利用推广后的筛法证明了：所有充分大的偶数都能表示成两个数之和，并且两个数的质因数个数都不超过 9 个。也就是说，所有「充分大」的偶数确实可以表示成两个数的和，但这两个数是合数，且这两个合数所包含的质因子个数小于等于 9 个。因此，布朗的证明一般被记作「9+9」，而哥德巴赫猜想就是「1+1」。

圆法和筛法为弱哥德巴赫猜想的证明提供了巨大的帮助。1937 年，苏联数学家维诺格拉多夫（Ivan Vinogradov）指出，充分大的奇数可以表示为三个质数的和。这一定理被称为维诺格拉多夫定理。他的学生博罗兹金（K. Borozdin）在 1939 年确定了这个「充分大」的下限是 3¹⁴³⁴⁸⁹⁰⁷。这样一来，数学家们只需要验证小于 3¹⁴³⁴⁸⁹⁰⁷ 的奇数都可以表示为三个质数的和，结合维诺格拉多夫定理，就可以完全证明弱哥德巴赫猜想了。

数学家们似乎看到了曙光。然而，博罗兹金给出的这个下限实在是太大了，即使是用今天的超级计算机也无法对比这个下限小的所有数进行验证。1989 年，陈景润和王元将这个下限降低到 1043000.5。这个优化的下限结果仍然比较大，但相对已经好了很多。2002 年，香港大学的廖明哲与王天泽把这个下限降低到了 e³¹⁰⁰[17]。虽然这个下限还是超过了计算机验证的范围，但比 1043000.5 来说又小了很多。

2013 年 5 月 1 日，法国国家科学研究院和巴黎高等师范学院的研究员 Helfgott 在线发表了两篇论文，宣布彻底证明了弱哥德巴赫猜想[18][19]。Helfgott 综合使用了圆法、筛法和「指数和」等统计方法，把维诺格拉多夫定理中的下限降低到了 10³⁰ 。同时，Helfgott 的同事 Platt 用计算机验证了在 10³⁰之下的所有奇数都符合猜想，从而彻底解决了弱哥德巴赫猜想。

圆法对于弱哥德巴赫猜想的证明提供了巨大的帮助。但圆法对于强哥德巴赫猜想似乎无能为力。前面讲到，1919 年布朗用推广后的筛法证明「9+9」问题。数学家们将强哥德巴赫猜想解决的希望放在了布朗提出的方法上。数学家们在 1924 年至 1963 年，分别证明了「7+7」（1924 年）、「6+6」（1932 年）、「5+5」（1938 年）、「4+4」（1938 年）、「3+4」（1956 年）、「3+3」（1956 年）、「2+3」（1957 年）、「1+6」（1932 年）、「1+5」（1962 年）、「1+4」（1956 年）以及「1+3」（1965 年）问题，逐渐与最终目标：强哥德巴赫猜想的「1+1」靠近。

中国数学家陈景润于 1973 年对筛法做出重大的改进，提出了一种新的「加权筛法」，并证明了「1+2」问题[20]。然而，陈景润几乎已经将筛法发挥到了极致，似乎很难用筛法证明最终的「1+1」问题了。强哥德巴赫猜想的解决或许需要新的数学工具。质数的个数

我们回到质数的定义中来。相信朋友们在五年级学习质数时，小学老师一定会让每一位同学背诵 100 以内的质数表吧？我依稀记得我的小学老师教授了我们下述口诀：

2、3、5、7 和 11，

13、19 和 17，

23 来 29，31 来 37，

41、43 和 47，

53、59、61，

67、71 和 73，

79、83、89，再加一个 97。

不过，小学数学老师没有让每一位同学背诵大于 100 的质数，当时我们每个人心里一定都为此怀有感激之心。然而，现在想来，为什么小学老师不再要求我们背诵大于 100 的质数呢？

一个可能的原因是没有大于 100 的质数，然而这显然是不正确的，因为经过尝试后我们会发现 101 就是一个质数。我们扩展一下这个疑问，质数是否有无限多个？答案是肯定的。人类很早以前就已经知道有无限多个质数。早在公元前的 200~300 年间，古希腊数学家欧几里得（Euclid）就在他著名的数学教科书《几何原本》中证明了质数有无限多个。

质数的分布与孪生质数猜想

第二个不需背诵大于 100 质数的可能原因是：质数在正整数之间出现的位置没有任何规律，只能通过死记硬背的方法记忆质数位置。用稍微数学一点的语言描述就是：质数在正整数中的分布似乎并无规律。18 世纪晚期，数学家们编制了一个巨大的质数表，试图寻找质数出现位置的规律，却并没有成功。不要说质数出现的位置了，就算求某个范围内质数的数量就已经非常困难。有多少个质数小于一个正整数 x 这样一个看似简单的问题都困扰了人类将近 200 年。当时，包括德国数学家高斯（Johann Carl Friedrich Gauss）和法国数学家勒让德（Adrien-Marie Legendre）等大数学家都有下述猜想，然而并没有找到严谨的证明。

当x无限增长时，不超过 x 的质数个数与 x/ln x 之比趋近于 1。（ln x 是 x 的自然对数）。

这个猜想后来被称为「质数定理」，简单来说就是：前 x 个正整数中大约有 x/ ln x 个质数。在质数定理提出后的大约 200 年，法国数学家阿达马（Jacques Hadamard）和比利时数学家瓦列-普金（Charles-Jean-Gustave-Nicholas de la Vallée-Poussin）才利用复变函数论在 1896 年首次证明了质数定理。虽然现在数学家们已经找到了不应用复变函数论证明质数定理的方法，但是所有已知的证明都非常复杂，远非原始结论这样清晰和简洁。

质数定理告诉我们，随着 x 的增大，质数在正整数中的分布会变得越来越稀疏。举例来说，100 以内有 25 个质数，质数占比为 25%。而 100 万以内的质数只占 100 万的 7.85%。这么看来，随着 x 的增大，每个质数之间相隔的距离平均来看也应该会越来越远。然而，事实似乎并非如此简单。这就涉及到与哥德巴赫猜想平级的「孪生质数猜想」[21]了。

所谓「孪生质数」，是指相差为 2 的质数对，例如：3 和 5、5 和 7、11 和 13，等等。用数学形式描述即为：质数对（p,p+2）为孪生质数。希尔伯特 1900 年报告中的第八个问题不仅回顾了哥德巴赫猜想，还提出了下面一个假设：

存在无穷多个质数 p，使得 p+2 也是质数。

1849 年，法国数学家波利尼亚克（Alphonse de Polignac）提出了一个更一般的「波利尼亚克猜想」：

对所有自然数 k，存在无穷多个质数对(p,p+2k)。

当 k=1 时，波利尼亚克猜想就是孪生质数猜想。

孪生质数猜想虽然不如哥德巴赫猜想那样著名，但其仍然被认为是一个公认的难题。2013 年 5 月 14 日，据《自然》（Nature）杂志报道[22]，华人数学家张益唐证明：存在无穷多个质数对，其相差都小于 7000 万。张益唐的论文已被国际数学旗舰期刊《数学年刊》（Annals of Mathematics）于 2013 年 5 月 21 日接受。华人数学家陶哲轩随后于 2013 年 6 月 4 日开始了一个名为「PolyMath」的计划[23]，邀请网上的志愿者们协助合作，降低张益唐的论文中所给出的 7000 万上限。截止至 2016 年 7 月 14 日，PolyMath 维基宣称上限已经降至 246[24]。

质数的判定

第三个可能的原因是很难找到一种快速方法判断一个正整数是否为质数。例如，339061 是否为一个质数？相信大家第一个反应就是用 339061 除以小于它的各个正整数，尝试找到一个因子。经过漫长而艰苦的人工计算后，我们最终会发现 339061=409×829，因此不是一个质数。判断某个正整数是否为质数的问题到现在为止依然困扰着数学界。这一问题在数学上被称为质数判定问题，或质性检测问题。

我们先看看特殊形式正整数的质数判定方法，没准会带来一定的突破呢？欧几里得在《几何原本》中指出，少量的质数可以写成 2p−1 的形式，其中 p 也是一个质数。1644 年，法国传教士梅森（Martin Mersenne）对形如 2p−1 形式的质数进行了研究。他提出了这样的论断：当 p=2,3,5,7,13,17,19,31,67,127,257 时，2p−1 是质数，而对于小于 257 的所有其它质数 p， 2p−1 都不是质数。数学家们花费了将近 300 年的时间研究了梅森给出的这一系列质数，并发现当 p=67 和 p=257 时， 2p−1 不是质数。与此同时，梅森给出的这一系列质数之间还遗漏了一些质数。1883 年，Pervushin 证明了 2⁶¹−1 是质数。1911 年和 1914 年，Powers 分别证明了 2⁸⁹−1 和 2¹⁰⁷−1 为质数。因梅森对这类质数的研究所做出的突出贡献，人们将形如 2p−1 的质数称为「梅森质数」。

梅森质数的发现历史也代表了人类寻找最大质数的历史。1876 年，法国数学家卢卡斯（François Édouard Anatole Lucas）证明了 2¹²⁷−1 是梅森质数。在这之后的 75 年间， 2¹²⁷−1 都保持了人类已知最大质数的记录。1876 年，卢卡斯总结并完善了一种检验梅森质数的快速方法。1930 年代，美国数学家莱默（Derrick Henry Lehmer）改进了卢卡斯所提出的算法。现今我们称这种梅森质数的快速检验方法为「卢卡斯-莱默质数检验法」（Lucas-Lehmer Primality Test）。电子计算机的发明革命化地改进了梅森质数的寻找。借助电子计算机的帮助，人类才通过卢卡斯-莱默质数检验法发现了更大的质数。1952 年，加州大学伯克利分校的美国数学家 Robinson 在莱默的指导下编写了计算机程序，利用位于洛杉矶加利福尼亚大学的西部自动计算机（Standards Western Automatic Computer，SWAC）发现了梅森质数 2⁵²¹−1 和 2⁶⁰⁷−1。

为了找到更大的梅森质数，毕业于麻省理工学院的 Woltman 于 1996 年发起了因特网梅森质数大搜索（Great Internet Mersenne Prime Search，GIMPS）项目。任何志愿者都可以从网站上免费下载开放源代码的 Prime95 和 MPrime 软件来搜索梅森质数。这一项目取得了巨大的成功。截止到 2016 年 1 月，GIMPS 共搜索到 15 个梅森质数。现在已知最大的梅森质数是 2016 年 1 月 7 日发现的 2⁷⁴²⁰⁷²⁸¹−1[25]，共有 22338618 位十进制数。第二大的梅森质数是 2013 年 1 月 25 日发现的 2⁵⁷⁸⁸⁵¹⁶¹−1，共有 17425170 位十进制数。

对于一个不是特殊形式的正整数 a，其质数判定就变成一个比较困难的问题了。最简单的方法是所谓的「试除法」，依次尝试用 除以小于 a 的数（实际上，试到 a 就足够了），看看是否可以整除。然而，对于比较大的正整数 a，尝试所有 种可能所带来的计算量实在是太大了。数学家们因此寻找各种方式，提高质数判定的效率。

1770 年，英格兰数学家华林（Edward Waring）与他的学生威尔逊（John Wilson）提出了一个判定某个正整数是否为质数的等价条件。历史上称这个结论为威尔逊定理。这对师生当时未能给出这一定理的证明。1773 年，法国籍意大利裔数学家拉格朗日首次证明了威尔逊定理。基于威尔逊定理的质数判定法效率有所提高，但是判定的过程要进行一次「阶乘」运算，此质数判定法的计算量仍然比较夸张。随后，数学家们又提出了多种质数判定方法，包括莱默判定法、普洛兹（Proth）判定法、波克林顿（Pocklington）判定法等。但这些判定方法都涉及到复杂的指数运算。对于大整数的质数判定来说，这些判定方法的效率还是太低了。

上述方法都可以 100% 判定某个正整数是否为质数，我们一般称这些判定法为「确定判别法」。既然确定判别法的效率太低，我们能否换一种思路：是否能判断一个比较大的正整数基本上应该是个质数呢？也就是说，找到某种方法对正整数进行测试，如果测试通过，则有比较大的概率判断此正整数是个质数。遵循这一思路的判定方法一般称为「概率判别法」。事实证明，概率判别法虽然丧失了一部分准确性，但判定速度比确定判别法要快得多。最先发现的质数概率判别法直接利用了 1636 年法国数学家费马（Pierre de Fermat）提出的费马小定理，这一方法被称为「费马概率判别法」。

提到费马，最广为人知的想必就是费马《页边笔记》中留下的这句话了：

我发现了一个美妙的证明，但是由于空白太小而没有写下来。

这句话指的就是「费马猜想」的证明。不曾想，这简单的一句话花费了数学家们超过 300 年的努力，才最终得到了猜想的完全证明。为了证明费马猜想，在横跨三个世纪的证明过程中诞生了代数几何中的「椭圆曲线」（在现代密码学中我们经常会用到它），以及群论中的「伽罗华理论」（同样是现代密码学构造的基石）。经过数学家们的不懈努力，1994 年英国数学家怀尔斯（Andrew John Wiles）最终完成了费马猜想的证明，使得费马猜想升级为「费马大定理」。相关证明结果发表在 1995 年的《数学年刊》（Annals of Mathematics）上[26]。是的，这和张益唐「孪生质数猜想」证明所发表的期刊相同。怀尔斯的完整证明一共有 109 页，怪不得 300 年前费马在《页边笔记》中写不下。

为了进一步提高质数概率判别法的效率，美国数学家Solovay 和德国数学家Strassen 于 1977 年提出了「Solovay-Strassen 概率判别法」[27]。然而，Solovay-Strassen 概率判别法并没有得到广泛的应用，但在思想上给予了数学家们很大的启迪。1976 年，卡内基梅隆大学的计算机系教授Miller 提出了一个基于广义黎曼猜想的质数确定判别法[28]。然而，广义黎曼猜想还没有得到证明，因此Miller 所提出的判别法暂时还无法使用。后来，以色列耶路撒冷希伯来大学的Rabin 教授对判别法进行了修改，提出了不依赖于广义黎曼猜想的质数概率判别法[29]。因 Miller 和 Rabin 对此判别法都做出了突出的贡献，这一判别法被命名为「Miller-Rabin 质数判别法」。现今，Miller-Rabin 质数判别法是最为常用的质数判别法，广泛用于密码学方案中的大质数选取步骤中。

最大公约数

有了质数的概念，我们就可以进一步回顾另一个广为人知的概念：「最大公约数」。能整除两个整数的整数成为这两个整数的「公约数」。例如，对于整数 24 和 36，整数 1、2、3、4、6、12 都可以整除 24 和 36，因此它们都是 24 和 36 的公约数。而最大公约数，顾名思义，就是公约数里面最大的那个。例如，12 是 24 和 36 公约数中最大的，因此 12 就是 24 和 36 的最大公约数。如果两个整数的最大公约数是 1，就称这两个整数「互质」。例如，17 和 22 的最大公约数是 1，因此 17 和 22 互质。

如何求两个整数的最大公约数呢？这里又出现了欧几里得的名字，可见欧几里得为数学做出了巨大的贡献。欧几里得在《几何原本》中记载了一个求解最大公约数的方法，这个方法也就被命名为「欧几里得法」。又因为这个方法的过程是依次进行多次除法，故这个方法又被称为「辗转相除法」。辗转相除法的效率比「分别求两个数的公约数，再找最大值的方法」高得多。我们这里不对方法做详细讲解，只要知道人类找到了快速求解最大公约数的方法就可以了。

(i) 回信原文为古德语：Dass aber ein jeder numerous par eine summa duorum primorum sey, halte ich für ein ganz gewisses theorem, ungeachtet ich dasselbe nicht demonstriren kann. 感谢金歌同学协助翻译.

同余算术：整数除法中的余数

同余与模数

讨论完了正整数 a 整除正整数 b 的情况，我们来看看应该如何处理正整数 a 不能整除正整数 b 的情况。前面提到过，有两种处理这一问题的方法：引入分数，或者引入余数。分数的引入已经耳熟能详了，我们来看看余数的引入会为我们带来哪些有趣的性质。

我们在日常生活中经常使用余数的概念。举个例子，假设现在的时间是 21 点。如果问从现在开始 50 个小时以后的时间（每天以 24 小时计时），我们就会自然而然地用 50 除以 24 后取余数，并把它加在当前时间上，得到 23 点这样的结果。

在第二条分支上，我们会对余数特别感兴趣，因此我们引入一个专门的记号来表示余数。令 a 和 b 为整数，m 为正整数，如果 m 可以整除 a−b，我们称 a 模 m 同余 b，并把 m 称为「模数」。这个同余关系用符号表示为 a≡b (modm)。我们可以利用时钟理解模数的概念。50 小时除以 24 小时，余数为 2 小时。这也就意味着 24 可以整除 50−2，我们称 50 模 24 同余 2，用符号表示为 50≡2(mod 24)。可以看出，模数在同余算术中起到了很大的作用。

既然负数引入的原因是加法和减法，分数引入的原因是乘法和除法，那么同余算数下是否也有加减乘除的概念呢？这个问题看起来比较简单，但深入了解后就会发现这是一个揭露质数性质的有趣问题。下面，我们根据模数的不同，分三种情况回答这个问题：模数为 2、模数为合数 n、模数为质数 p。为了论述方面，之后如无特别说明且不引起歧义，我们把同余符号≡简单地写成=，并略去 mod 符号。

模数为 2 的运算：计算机的数学基础

当模数为 2 时，能参与运算的就剩下 0 和 1 了，这有什么可讨论的呢？既然只剩下了 0 和 1，我们干脆在模数为 2 的条件下把各种情况下的加减乘除的运算及运算结果都列出来好了。

•  0 与 0 的运算：0+0=0，0−0=0 ，0×0=0，0÷0 无意义；

•  0 与 1 的运算：0+1=1，0−1=？，0×1=1，0÷1=0；

•  1 与 0 的运算：1+0=1，1−0=1，1×0=0，1÷0 无意义；

•  1 与 1 的运算：1+1=？，1−1=0，1×1=1，1÷1=1。

我们遇到了两个有点麻烦的问题，第一个是 1+1 的结果。要说 1+1 应该等于 2，但这里是模数为 2 的同余运算，只剩下 0 和 1 这两个数，但加法运算结果超过 0 和 1 了。这怎么办？没关系，既然同余运算的定义是取余数，我们把结果除以 2 取余数就好了。2 除以 2 的余数为 0，所以我们有 1+1=0。

第二个是 0−1 的结果。要说 0−1 应该等于−1，但这里是模数为 2 的同余运算，根本没有负数的概念，怎么办？回想之前我们对负数的另一种理解：负数是与某个正数相加后结果为 0 的数。因此我们可以把 0−1 写为 0+(−1)，而所谓的 −1 就是与 1 相加后结果为 0 的数。谁与 1 相加后结果是 0 呢？就是上一段提到的 1，1+1=0。因此有 0+(−1)=0+1=1。

模数为 2 的运算就这么多，实际中有什么应用呢？模数 2 造就了计算机的诞生。

计算机到底是如何工作的？刘慈欣的著名硬科幻小说《三体》的第 17 章：三体、牛顿、冯·诺依曼、秦始皇、三日连珠[30]，就介绍了计算机的工作原理。我们先来看看冯·诺依曼为秦始皇构建的第一个部件：

「我不知道你们的名字，」冯·诺伊曼拍拍前两个士兵的肩，「你们两个负责信号输入，就叫『入 1』、『入 2』吧。」他又指指最后一名士兵，「你，负责信号输出。就叫『出』吧，」他伸手拨动三名士兵，「这样，站成一个三角形，出是顶端，入 1 和入 2 是底边。」

「哼，你让他们成楔形攻击队形不就行了？」秦始皇轻蔑地看着冯·诺伊曼。牛顿不知从什么地方掏出六面小旗。三白三黑，冯·诺伊曼接过来分给三名士兵，每人一白一黑，说：「白色代表 0，黑色代表 1。好，现在听我说，出，你转身看着入 1 和入 2，如果他们都举黑旗，你就举黑旗，其他的情况你都举白旗，这种情况有三种：入 1 白，入 2 黑；入 1 黑，入 2 白；入 1、入 2 都是白。」

计算机用位（bit）表示信息，每个位只有两个可能的值，即 0 或者 1。在故事中，我们把白旗看作 0，把黑旗看作 1。冯·诺依曼构建了 0 和 1 的第一种运算关系：「与」。从描述中我们可以看到，随着运算的‘入’不同，运算结果的‘出’也不同。冯·诺依曼构建的第一个运算关系的全部运算结果可以用表 2 描述：

入1

入2

出

运算关系

0

0

0

0×0=0

0

1

0

0×1=0

1

0

0

1×0=0

1

1

1

1×1=1

表 2：冯·诺依曼构建的运算关系「与」

稍微对比一下我们就可以看出，这个运算关系和模 2 下的乘法运算有异曲同工之妙！既然与运算是模 2 下的乘法，那么冯·诺依曼构建的下一个运算关系会是模 2 下的加法吗？

冯·诺伊曼转向排成三角阵的三名士兵：「我们构建下一个部件。你，出，只要看到入 1 和入 2 中有一个人举黑旗，你就举黑旗，这种情况有三种组合——黑黑、白黑、黑白，剩下的一种情况——白白，你就举白旗。明白了吗？好孩子，你真聪明，门部件的正确运行你是关键，好好干，皇帝会奖赏你的！下面开始运行：举！好，再举！再举！好极了，运行正常，陛下，这个门部件叫或门。」

冯·诺依曼所构建的第二种运算关系称为「或」，其全部运算结果可以用下表 3 描述：

入 1

入 2

出

0

0

0

0

1

1

1

0

1

1

1

1

表 3：冯·诺依曼构建的运算关系「或」

感觉和加法运算没什么关系，我们继续往后看：

然后，冯·诺伊曼又用三名士兵构建了与非门、或非门、异或门、同或门和三态门，最后只用两名士兵构建了最简单的非门，出总是举与入颜色相反的旗。

我们注意到有一个运算关系为「异或」。异或运算是指，如果两个「入」所举的旗子是同一个颜色，「出」就举白旗；如果两个「入」所举的旗子不是同一个颜色，「出」就举黑旗。异或运算的全部结果可以用表 4 描述：

入1

入2

出

运算关系

0

0

0

0+0=0

0

1

1

0+1=1

1

0

1

1+0=1

1

1

0

1+1=0

表 4：冯·诺依曼构建的运算关系「异或」

这个运算关系和模 2 下的加法运算又有异曲同工之妙！

实际上，使用与、异或和「出总是举与入颜色相反的旗」的「非」这 3 种基本运算就可以实现计算机中的所有运算关系。若把非运算看作「入 2」固定为 1 的异或运算（运算结果如表 5 所示），我们完全可以用模 2 下的加法和乘法运算表示计算机中的全部运算关系。

入1

入2（固定）

出

运算关系

0

1

1

0+1=1(mod 2)

1

1

0

1+1=0(mod 2)

表 5：运算「非」和「与」的关系

而计算机正是这些简单的运算构成的，正如冯·诺依曼之后所说：

「不需要，我们组建一千万个这样的门部件，再将这些部件组合成一个系统，这个系统就能进行我们所需要的运算，解出那些预测太阳运行的微分方程。这个系统，我们把它叫做……嗯，叫做……」

「计算机。」汪淼说。

人类通过模 2 这样一个最为基本的同余运算，就可以用数学方式描述计算机的计算模式了。

模数为 n：有点复杂

我们再来看看当模数为合数 n 时会发生什么。当模数为 n 时，可以参与运算的数为所有小于 n 的整数了，即：0、1、2、…、n−1，一共有 n 个数。其实，模数为 n 的情况特别复杂。为了简单起见，我们这里只考虑 n 为两个质数乘积的形式，就以 n=10=2×5 为例好了，因为 10 是 2 和 5 这两个质数的乘积，并且模 10 取余数很简单：看结果的个位即可。

首先要解决减法和负数问题。模数为 n 时的解决方法和模数为 2 的解决方法相似。对于小于 n 的任意数 a，哪个数和 a 相加的结果等于 0 呢？结果很简单，n−a。首先 n−a<n 是肯定满足的。其次，a+(n−a)≡a−a+n≡n≡0 (modn)。这样，我们就成功的解决了模数为 n 时加法的全部问题。例如，n=10 时，小于 10 的数所对应的负数如表 6 所示。

a

0

1

2

3

4

5

6

7

8

9

-a

0

9

8

7

6

5

4

3

2

1

表 6：模 n=10 下的负数表

然后要解决除法和倒数的问题。对于 0 来说很简单，任何数乘以 0 还是 0；0 除以任何数也是 0；任何数除以 0 都没有意义。但对于不是 0 的数来说，除法和倒数的问题解决起来就有那么一点复杂了。根据前面的描述，我们要对小于 n 的数 a 找到 a⁻¹，要求 a 与 a⁻¹ 相乘的结果在模 n 下等于 1，即 a×a⁻¹≡1 (modn)。

然而，很快我们就会发现，对于有些 a 来说，可以找到 a⁻¹，例如，n=10 时，对于 a=3，我们有 3×7≡21≡1 (mod 10)，因此 a⁻¹=7。但是对于有些 a 来说，我们却找不到这样的数。例如，n=10 时，对于 a=2：2×1=2，2×2=4，2×3=6，2×4=8，2×5=0，2×6=2，2×7=4，2×8=6，2×9=2，根本没有等于 1 的。这怎么办？

干脆，我们把所有能找到 a⁻¹ 的 a 都列出来，看看有没有什么规律。n=10 时， a⁻¹ 的找寻结果如表 7 所示。

a

1

2

3

4

5

6

7

8

9

a⁻¹

1

\

7

\

\

\

3

\

9

表 7：模 n=10 下的负数表

有什么规律吗？我们首先可以观察到：偶数都找不到。那 5 找不到又是个什么情况？等等，当 a 和模数 10 的最大公约数为 1 时，也就是 a 和 10 互质时，就能找到 a⁻¹；反之，当 a 和模数 10 不互质，就找不到 a⁻¹。实际上，数学家们已经证明：对于任意 a<n，只有当 a 与 n 互质，才能找到 a−1。给定满足与 n 互质的 a，怎么才能快速找到 a⁻¹ 呢？总不能一个一个去试吧？实际上，利用前面提到的辗转相除法，就可以快速找到 a⁻¹。

在小于 n 的所有整数中，与 n 互质的数有多少个呢？当 n=10 时，一共有 1、3、7、9 这 4 个数满足条件。实际上，当 n=p×q，其中 p 和 q 为质数时，满足条件的数共有 (p−1)(q−1) 个。例如，当 n=10=2×5 时，我们可以得到 (2−1)(5−1)=4。如果 n 有更多的质数因子，满足条件数的个数计算会变得稍微复杂一些。我们把满足小于 n，且与 n 互质的数总个数用一个函数 φ(n) 来表示。这个函数叫做「欧拉函数」（Euler Function），没错，这个欧拉就是和哥德巴赫写信的欧拉。

既然与模数 n 互质的数 a 都能找到 a⁻¹ ，这些数是不是还有什么其它的性质？我们列举这些数的两个非常重要的性质。

第一，这些数在模 n 下互相之间进行乘法运算，结果仍然是这些数。一般来说，如果一些数互相之间运算后结果还在这些数之内，我们称这些数在此运算下具有「封闭性」。我们列举一下 n=10 的情况。与 10 互质的数为 1、3、7、9，我们有：

•  1 与其它数的乘法运算：1×3=3，1×7=7，1×9=9

•  3 与其它数的乘法运算：3×1=3，3×3=9，3×9=7

•  9 与其它数的乘法运算：9×1=3，9×3=7，9×9=1

第二，如果我们对这些数求「幂」，会有更有趣的结果。所谓幂运算，就是让数自己和自己相乘，把乘多少次写在右上角。例如，在自然数条件下， 3 4 =3×3×3×3=81。我们试试在模 n=10 的条件下计算这些数的「幂」，结果如表 8 所示（注意，规定 a 0 =1）。

a

1

3

7

9

a⁰

1

1

1

1

a¹

1

3

7

9

a²

1×1=1

3×3=9

7×7=9

9×9=1

a³

1×1×1=1

3×3×3=7

7×7×7=3

9×9×9=9

a⁴

1×1×1×1=1

3×3×3×3=1

7×7×7×7=1

9×9×9×9=1

表 8：模 n=10 下的幂运算结果表

观察结果后我们会发现，对于所有的 a，都有 a⁴=1。4 这个数怎么这么眼熟呢？对了！4 就是这些数的总个数。事实上，在模 n 下对所有存在倒数的数求其 φ(n) 的幂，结果都为 1。

更有意思的是，对于 3 和 7 来说，a⁰、a¹、a²、a³ 的结果能把 1、3、7、9 各得到一遍（虽然得到的顺序不太一样），到 a⁴=1 又循环回了 1。事实上，在模 n 下一定能找到一个数 g，使得 g⁰、g¹、…、gφ(n)−1把所有与 n 互质且小于 n 的正整数各得到一遍，看起来就好像 g 把所有这些数都生成（Generate）了一遍。因此，我们把满足这种条件的数称为「生成元」（Generator）。

有关模 n 条件下的一些性质我们就讲到这里。

模数为 p：规整了很多

我们最后来看看当模数为质数 p 时会发生什么。当模数为 p 时，可以参与运算的数为 0、1、2、…、p−1 这 p 个数。我们用与 10 最近的质数 11 为例。

减法和负数问题很容易解决。对于小于 p 的任意数 a，哪个数和 a 相加的结果等于 0 呢？同样是 p−a。例如，p=11 时，每个小于 11 的数所对应的负数如表 9 所示。

a

0

1

2

3

4

5

6

7

8

9

10

-a

0

10

9

8

7

6

5

4

3

2

1

表 9：模 p=11 下的负数表

p 是质数为除法和倒数问题的解决带来了很大的便利，因为所有小于 p 的整数都与 p 互质。这样一来，所有小于 p 的整数 a 都能找到 a⁻¹ 了，欧拉函数的形式也非常简单：φ(p)=p−1。p=11 时， a⁻¹ 的结果如表 10 所示。

a

1

2

3

4

5

6

7

8

9

10

a⁻¹

1

6

4

3

9

2

8

7

5

10

表 10：模 p=11 下的倒数表

模数为 n 的其它性质在模数为 p 时依然满足。第一，显然这些数在乘法运算下仍具有封闭性，反正所有小于 p 的数都在里面了。第二，任意 a 求「幂」同样满足 aφ(p)=ap−1=1，也同样存在生成元。模 p=11 时各个数的求「幂」结果如表 11 所示。

A

1

2

3

4

5

6

7

8

9

10

a⁰

1

1

1

1

1

1

1

1

1

1

a¹

1

2

3

4

5

6

7

8

9

10

a²

1

4

9

5

3

3

5

9

4

1

a³

1

8

5

9

4

7

2

6

3

10

a⁴

1

5

4

3

9

9

3

4

5

1

a⁵

1

10

1

1

1

10

10

10

1

10

a⁶

1

9

3

4

5

5

4

3

9

1

a⁷

1

7

9

5

3

8

6

2

4

10

a⁸

1

3

5

9

4

4

9

5

3

1

a⁹

1

6

4

3

9

2

8

7

5

10

a¹⁰

1

1

1

1

1

1

1

1

1

1

表 11：模 p=11 下的幂运算结果表

从表 11 的计算结果也可以看出，2、6、7、8 通过幂运算可以把所有小于 11 的数各得到一遍。这些数就是模 11 下的生成元了。

看似简单却又如此困难：整数分解问题与离散对数问题

同余和模数的引入使得质数包含了有趣的性质，而且似乎也挺好理解的，有什么比较难的问题吗？下面我们就来看看与质数相关的两个非常重要的困难问题：整数分解问题与离散对数问题。

数学家们很早就意识到，质数是构造正整数的积木。如果哥德巴赫猜想是对的，那么所有大于 2 的偶数都可以表示为 2 个质数的和；所有大于 5 的奇数都可以表示为 3 个质数的和。然而，还可以通过另一种方法用质数表示正整数。这个方法描述起来似乎有点麻烦，但是证明比较简单，它叫做「算术基本定理」。

算术基本定理：每个大于 1 的正整数或者为质数，或者可唯一地写为两个或多个质数的乘积。

虽然小学老师没有详细讲过这个定理，但这个定理确实挺好理解的，简单来说就是每个正整数都可以分解成质数因子相乘的形式。来看几个例子：

•  100 是一个合数，可以写为：100=2×2×5×5=2²×5²；

•  999 是一个合数，可以写为：999=3×3×3×37=3³×37；

•  1024 是一个合数，可以写为：1024=2×2×2×2×2×2×2×2×2×2=2¹⁰。

然而，算术基本定理只是告诉数学家们合数可以写为两个或多个质数的乘积形式，但是没有具体告诉数学家们具体怎么进行合数的质数分解。对于比较小的合数，我们可以尝试用它除以各个正整数，通过看是否能够整除来找到质因子。但是如果合数太大，这种方法的效率就会变得非常低。这个问题到现在为止依然困扰着数学家们。这个问题被称为「整数分解问题」（Integer Factorization Problem）[31]。

整数分解问题虽然没有被解决，但因为一直以来也一直没有找到应用方法，所以数学家们对解决这个问题动力也有所不足。然而，「现代密码学」诞生的标志之一，「公钥密码学」的出现，特别是 Rivest，Shamir 和 Adleman 提出了「RSA 算法」之后（我们后面就会详细讲解 RSA 算法），使得整数分解问题重新站到了历史的舞台上，这是因为 RSA 算法安全的原因正是由于整数分解问题是一个很困难的问题。

为了确定人类可以解决整数分解问题的难度，也为了衡量 RSA 算法的安全性，Rivest，Shamir 和Adleman 组建的「RSA 实验室」[32]于 1991 年 3 月 18 日发起了「RSA分解挑战」项目[33]，号召全世界的研究者们研究整数分解问题。他们的具体做法是：公开一系列不同长度的，由两个大质数相乘得到的合数，并邀请全世界的研究者们分解这些合数。合数的大小从 100 位十进制长一直到 617 位十进制长（依次称为 RSA-100, …, RSA-2048）。如果分解成功，RSA实验室将会支付一笔数额不菲的奖金。成功分解 RSA-2048 所对应的奖金达到 200000 美元！这些合数被称为「RSA 数」。RSA 分解挑战项目极大地激发了全世界研究者对于整数分解问题的探究。

在 RSA 分解挑战项目开始后不到 2 周，RSA-100 就在 1991 年 4 月 1 日被分解出来了。分解出 RSA-100 的学者是 Lenstra，他因此也获得了 1000 美元的奖金。一年以后的 1992 年 4 月 14 日，Lenstra 和 Manasse 分解出第二个RSA数：RSA-110，奖金为 4429 美元。后来，更大的 RSA 数被成功分解。到 2005 年，来自德国波恩大学的Franke 等人成功分解了RSA-640，获得了 20000 美元的奖金。

由于人类对于密码学理解的不断深入，RSA实验室认为没有必要继续进行 RSA 分解挑战项目了。因此，RSA 分解挑战项目于 2007 年终止[34]。然而，全世界的研究者们至今还在致力于解决 RSA 分解挑战。截止目前，被分解的最大 RSA 数为 Kleinjung 等人于 2009 年 12 月 12 日成功分解的 RSA-768，不过这里的 768 指的是此合数的二进制长度，其对应的十进制长度为 232 位。

另一个困难问题理解起来就不像整数分解问题那样直观了。我们前面讲到，对于与模数 n 互质且小于 n 的所有整数中，存在一个生成元 g，使得 g⁰、g¹、…、gφ(n)−1 会把所有小于 n 的数各得到一遍。在模 n 条件下，给定生成元 g 和某个小于 n 的正整数 a，可以通过一个称为「同余幂」的算法快速得到 b=ga。由于生成元的特殊性，数学家们也知道对于任意一个小于 n 的正整数 b，一定存在一个小于 n 的正整数 a，使得 b=ga 。但我们会发现，得到的顺序并没有什么规律。例如，当 n 为质数 p=11，g=2 时，得到的顺序如表 12 所示，感觉毫无规律。

2⁰

2¹

2²

2³

2⁴

2⁵

2⁶

2⁷

2⁸

2⁹

2¹⁰

1

2

4

8

5

10

9

7

3

6

1

表 12：模 p=11 下的倒数表

是否存在一种方法能快速得到满足条件的 a 呢？这个问题和实数上的求对数很像：如果在实数上，我们知道 a=log gb ，而且用计算器就可以很快得到结果。但这个问题在模 n 条件下就变得特别困难。这个问题被称为「离散对数问题」（Discrete Logarithm Problem）[35]。

我们了解到，人类现在已经成功分解了 232 位的 RSA 数，那么离散对数问题有没有对应的记录呢？也是有的，我们这里仅介绍模数为质数 p 的情况。2005 年 6 月 18 日，Joux 和 Lercier 宣布，它们应用了一个主频为 1.15GHz，具有 16 核的 HP AlphaServer 计算机，花费了 3 周的时间，使用筛法解决了十进制 130 位长强质数下的某一个数的离散对数问题[36]。2007 年 2 月 5 日，Kleinjung 宣布，它应用并行计算技术，通过多种计算机进行并行处理，最终使用筛法解决了十进制 160 位长安全质数下某一个数的离散对数问题[37]。2014 年 6 月 11 日，Bouvier、Gaudry、Imbert、Jeljeli 和 Thomé 同样使用筛法解决了十进制 180 位长安全质数下某一个数的离散对数问题[38]。模数为质数 p 的离散对数问题计算最新进展于 2016 年 6 月 16 日公布，Kleinjung、Diem、Lenstra、Priplata、Stahlke 宣布，它们从 2015 年 2 月开始，经过 1 年 4 个月的计算，应用了 6600 个主频为 2.2GHz 的 Intel Xeon E5-2660 处理器，最终成功应用筛法得到了十进制 232 位长安全质数下某一个数的离散对数问题。注意，以上所有的成果只是找到了某一个数的离散对数。要是求解所有数的离散对数，即使使用现在最先进的计算机处理器，所花费的时间估计也是个天文数字。

有关同余和模数的性质我们就介绍到这里。既然模数为 2 解决了计算机的计算过程描述问题，那么模数为 n 和模数为 p 能为我们带来什么呢？特别是整数分解问题和离散对数问题，真的只能作为一个困难问题困扰数学家吗？1976 至 1977 年，人类终于找到了困难问题的使用方法。而人类找到使用方法的日子，就是现代密码学诞生的日子。

古典密码学：技巧的较量

信息的加密和解密贯穿于人类的外交和战争史。可以说，密码学的发展离不开人类对安全通信的需求。我们首先简要回顾人类对加密和解密算法的探知过程。这部分内容并不涉及质数。（古典密码学的发展历史参考了《密码的奥秘》中的相关内容。）

最古老的加密设备：斯巴达密码棒

我们所熟知的最古老加密设备为「斯巴达密码棒」（Scytale），其被广泛适用于公元前 7 世纪的古希腊军事重镇斯巴达。所谓的密码棒就是一根木质的棒子。加密时，发送方把羊皮纸或者皮革带一圈接一圈地缠绕在密码棒上，然后沿着棒子的方向逐行写下完整的信息。信息写完后，将羊皮纸或者皮革带从密码棒上解下来，就得到了一个看上去毫无意义的字母带。接收者收到字母带后，将字母带缠绕在自己的密码棒上，只要接收者和发送者所用的密码棒长度和面数都相同，接收者就可以方便地读取隐藏的信息。

图 2：斯巴达密码棒

http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/Skytale.png/220px-Skytale.png

我们用图来表示密码棒的使用方法。在下面的例子中，信息「THE SCYTALE IS A TRANSPOSITION CIPHER」按照图 3 的方法写在缠在密码棒上的整条皮带上。

图 3：用斯巴达密码棒加密信息「THE SCYTALE IS A TRANSPOSITION CIPHER」

http://www.guokr.com/blog/425174/

写好后，把皮带从密码棒上解下来，结果就呈现为：TNSEHCPIEIOSSPSACHITYETRTRIAAONL。

斯巴达密码棒的加密方法本质上只是打乱了信息的字母顺序。想破解斯巴达密码棒的方法也非常简单，感兴趣的读者们可以试着解读一下，「USSONIERDENCEGDEREFS」对应的原始消息是什么呢？

格栅密码

斯巴达密码棒的加密方法可以看作「格栅」密码的一种。格栅密码是意大利数学家卡尔达诺所发明的加密方法。该方法的原理是，发送方和接收方约定一个栅格和消息的撰写方法。斯巴达密码棒所约定的栅格就是密码棒本身。格栅密码原理上非常简单，但是人们可以在栅格的构造方法中使用非常复杂的技巧。

最为经典的格栅密码是「格子」密码（The Trellis Cipher）[39]，也叫做棋盘密码，其加密方法如图 4 所示。假设待加密的信息是「I WILL BE AT THE NATIONAL GRAND OPERA TODAY.」开始时，将黑色格子置于左边最顶端，在白色格子中垂直书写信息。第二步，在书写 18 个字符之后将棋盘旋转 90 度，这样白色格子就被置于左边最顶端了，继续书写信息。第四步，移除格子，从左到右读取字母：ALDTTIIREENALLOHOOWAARAYGBPEDNINTAT.就是最终的加密结果了。

图 4：用格子密码加密「I WILL BE AT THE NATIONAL GRAND OPERA TODAY」

格栅密码还存在很多变种：栅格可以被设计的更复杂，格子数量可大可小。栅格的使用方法也可以多种多样：可以按照任意角度旋转栅格，可以正反使用栅格，栅格的旋转起点和顺序也可以随意设置。在第一次世界大战中的 1916 年，德国军队就曾在短期内使用格栅密码加密战场信息。但是由于格栅密码仍然不够安全，所以在几个月后就被德国军队弃用了。

单表代换密码

上述密码使用起来虽然方便，但不够安全的最主要原因是：本质上我们只是对发送消息的字母顺序进行了扰乱，并没有对字母进行修改。只要破解者知道或者部分知道字母扰乱的方法，就可以破解密码了。随着对密码研究的深入，人类发现加密信息的本质是使用一种发送方和接收方都知道的一个秘密对信息进行处理。只要接收方知道秘密，他就能从加密结果中正确恢复出信息。而作为不知道秘密的破解者，对加密结果就无能为力了。我们之后将发送的信息称为「明文」（Plaintext），将加密结果称为「密文」（Ciphertext），而双方都知道的秘密信息称为「密钥」（Secret Key）。

第一个涉及密钥的加密方法是罗马将军和独裁者凯撒大帝建立的加密方法，称为「凯撒密码」（Caesar Cipher）。凯撒大帝在高卢参加竞选时，在与他的罗马朋友和同事的私人信件中使用了这种加密方法。这个密码对明文进行了简单的移位处理。举例来说，如果明文是字母 A，则向后移位 3 个字母，A 被加密为 D。同理，B 被加密为 E，C 被加密为 F，一直到 W 被加密为 Z。对于 X 来说，移位 3 个字母超过了Z，则返回到字母 A。因此，X 被加密为 A，Y 被加密为 B，Z 被加密为 C。如果接收方也知道要移位 3 个字母，则在解密时把密文往前移位 3 个字母即可。这里，移位的字母数量 3 就可以看成凯撒密码的密钥。举个例子，当移位字母数量为 4 时，信息「REINFORCEMENTS ON THE WAY」的加密结果为：「VIMRJSVGIQIRXW SR XLI AEC」。凯撒密码的缺点是密钥的个数实在是太少了，只有 25 种可能。如果破解者知道密文是由凯撒密码加密的，他可以试遍所有 25 种可能的移位方式，达到解读密文的目的。

图 5：尤里乌斯• 凯撒大帝雕像

https://zh.wikipedia.org/wiki/%E5%B0%A4%E5%88%A9%E7%83%8F%E6%96%AF%C2%B7%E5%87%B1%E6%92%92#/media/File:Bust_of_Gaius_Iulius_Caesar_in_Naples.jpg

凯撒密码实际上是一种「单表代换密码」。所谓单表代换密码，就是把消息中的字母一一替换为另一个字母。例如，当密钥为 3 时，凯撒密码的字母代换表如图 6 所示。

图 6：凯撒密码的字母代换表

既然凯撒密码的缺陷是可能的密钥个数太少，那么我们能不能进一步改进凯撒密码呢？我们制作一个类似凯撒密码的字母代换表，但是每个字母的移位次数并不是固定的。举个例子，我们可以让 A 变为 D，B 变为 C，C 变为 E，以此类推，只要 26 个字母互相之间仍然满足一一映射关系即可。发送方和接收方的密钥就是字母的映射表。这样一来，可能的密钥个数就从 25 个一下扩展成为 26×25×24⋯4×3×2 个，约为 4×10²⁶，是个非常大的数。

更进一步，字母的映射结果不一定还是字母。我们还可以把字母映射成各种符号。最为经典的非字母映射莫过于「猪圈密码」[40]了。由于在 1700 年代，共济会常常使用这种密码进行秘密通信，所以猪圈密码又被称为「共济会密码」。猪圈密码的符号与 26 个字母的对应关系如图 7 所示。如果用猪圈密码加密明文「X MARKS THE SPOT」，则密文如图 8 所示。

图 7：猪圈密码的符号与 26 个字母的对应关系图

https://zh.wikipedia.org/wiki/%E8%B1%AC%E5%9C%88%E5%AF%86%E7%A2%BC#/media/File:Pigpen_cipher_key.svg

如果把猪圈密码和前面提到的改进凯撒密码进行组合后，看起来是一个非常不错的加密方法。古典密码学中有很多类似的方法。这一系列方法在密码学中被称为「单表代换密码」，这是因为本质上我们还是利用了一个字母与字母/图像的一一映射表格对明文进行加密。

图 8：利用猪圈密码加密「X MARKS THE SPOT」的结果

https://zh.wikipedia.org/wiki/%E8%B1%AC%E5%9C%88%E5%AF%86%E7%A2%BC#/media/File:A-pigpen-message.svg

单表代换密码看起来已经是一个非常不错的密码了。然而，这种密码仍然有内在的缺点。由于字母与字母/符号是一一对应的，这就意味着相同明文的代换结果也一定是相同的。然而，语言一般都有其本身的特性。我们可以利用语言本身的特性从加密结果中分析出一些结果。

图 9：英文中字母出现的频率表

https://upload.wikimedia.org/wikipedia/commons/thumb/d/d5/English_letter_frequency_(alphabetic).svg/2000px-English_letter_frequency_(alphabetic).svg.png

以英文为例。英文中每个字母出现的频率是不一样的。随着文本长度的增长，这种规律会愈发明显。图 9 给出了英文中字母出现的频率分布。我们可以看出，字母E在英文中出现的概率最高。随后是 T，A，O 等。由于单表代换密码中，相同字母的代换结果一定相同，因此破解者可以通过分析加密结果中字母/符号出现的频率对单表代换密码进行破译。我们可以考察加密结果中哪个字母出现的频率最高，那个字母的明文很可能就对应 E。另一方面，英文中固定词语出现的频率也会非常高。常用的简单单词，如 THE、IT、IS 等都会频繁出现在发送的信息中。通过英文单词本身的规律，加上适当的尝试后，破解者很可能恢复出明文，同时将字母的映射表也一并恢复出来。

多表代换密码

人类需要更加安全的加密方法。意大利文艺复兴时期的天才阿尔伯蒂（Leon Battista Alberti）[41]进一步改进了凯撒密码，并在加密过程中使用了多字母映射表。阿尔伯蒂的此种加密方法在 1553 年被意大利人贝拉索（Giovan Battista Bellaso）[42]改进，并由法国人维吉尼亚（Blaise de Vigenère）[43]所推广。因此，这个密码被称为「维吉尼亚密码」（Vigenère Cipher）[44]。维吉尼亚密码是一个相对很安全的加密系统，自提出后的 300 多年间都未得到破解。因此，这一密码很长时间以来都享有至高荣誉：无法破译的密码（Le chiffre indéchiffrable）。

图 10：维吉尼亚

https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher#/media/File:Vigenere.jpg

然而，维吉尼亚密码也不是安全的。事实上，以维吉尼亚密码为代表的「多表代换密码」均有安全漏洞。1863 年，德国人卡斯基（Friedrich Kasiski）[45]公开了一份针对维吉尼亚密码等多表代换密码的破解方法，称为「卡斯基检测法」[46]。不过有间接证据表明，早在 1863 年之前的 10 年，英国数学家巴贝奇（Charles Babbage）[47]也提出了类似的破解方法。

恩格玛机

军事活动一直是加解密的核心场景。多表代换密码变得不安全后，如何秘密地传递信息重新成为了军事活动中的核心问题。如果传输的军事情报被对方获取并破解，对方就可以根据情报采取行动，在战争中取得巨大的优势。但是，更加安全的加密方法一般意味着更加复杂的加密和解密过程，手工加解密的方式已经变得不太可行。一方面，复杂的加解密过程容易导致发送方在手工加密时发生错误，从而导致接收方无法正确解密密文。另一方面，手工加解密的速度较慢，这会使得友军就无法及时恢复明文，使得发送的明文丧失一定的时效性。

为了方便加密和解密，同时保证安全性，人类开始考虑设计精巧的机器，让机器帮助人类实现信息的快速加解密。在二次世界大战期间，人类发明了多种加密机器。在第二次世界大战期间，英国使用了被称为「X型」（Type X）的密码机[48]。美国人使用了更为先进的「SIGABA」（或称「M-134」）密码机[49]。然而，最为经典的加密机则是第二次世界大战时德军所使用的「恩格玛机」（Engima Machine）[50]。

德国工程师 Arthur Scherbius 于第一次世界大战的末期出于商业用途发明了恩格玛机。它的出现很快得到了德国军方的注意。图 11 为恩格玛机，它由 4 个部分组成：

•  最上面是 3 个「转子」（Rotors），用于设置密钥；

•  然后是「灯盘」（Lampboard），发送方/接收方可以从灯盘上快速得到加密/解密结果；

•  再往下是「键盘」（Keyboard），发送方/接受方通过键盘输入明文/密文；

•  最下面是「插接板」（Plugboard），同样用于设置密钥。

图 11：恩格玛加密机

https://upload.wikimedia.org/wikipedia/commons/3/3e/EnigmaMachineLabeled.jpg

恩格玛机具有两个非常重要的优势。第一，恩格玛机的使用非常方便。设置好密钥和加密/解密模式后，发送方/接收方只需要在键盘上按下明文/密文，灯盘上就会对应地显示密文/明文。图 12 是恩格玛机的使用演示。可以看出，当按下明文 N 时，灯盘上的字母 Y 就被点亮，Y 就是 N 的加密结果。

图 12：恩格玛加密机加密演示

Numberphile 制, 阿尔法小分队科教组译. 158,962,555,217,826,360,000 (Enigma Machine).

http://www.bilibili.com/video/av2883992/. 01 分 16 秒

第二，恩格玛机非常便携。恩格玛机的体积不大，易于携带。德军可以将恩格玛机装在军舰、飞机、甚至坦克上。

第三，恩格玛机的密码似乎非常安全。最初的恩格玛机的转子只有 3 个，插接板也没有那么复杂，还不够安全。波兰密码学家 Marian Rejewski、Jerzy Różycki 和 Henryk Zygalski 研制出了名为「炸弹」的电子计算机，用来对其进行破解。1938 年，恩格玛机将转子个数由 3 个增加到 5 个，使用时需要选择正确的 3 个转子，并按照正确的顺序安装在恩格玛机。与此同时，插接板也变得更加复杂，一共需要正确连接插接板上的 10 对字母。如此的设定使得德军认为恩格玛机是一个牢不可破的系统（Unbreakable System）。

恩格玛机的密钥一共有多少种可能呢？首先，要从 5 个转子中选择 3 个转子，按照正确的顺序安装在恩格玛机上。其次，每个转子有 26 个初始位置，加解密时，每个转子的 26 个初始位置都要正确设定。最后，要按照图 13 的方法，用插线在插接板上正确连接 10 对字母，有其中一对连接错误都不行。

图 13：恩格玛加密机的插接板连接演示

Numberphile 制, 阿尔法小分队科教组译. 158,962,555,217,826,360,000 (Enigma Machine).

http://www.bilibili.com/video/av2883992/. 07 分 39 秒

经过计算可以得到，恩格玛机的密钥总数为 158,962,555,217,826,360,000。即使到了现在，用最快的计算机尝试所有密钥也几乎是不可行的。

图 14：恩格玛加密机的密钥总数

Numberphile 制, 阿尔法小分队科教组译. 158,962,555,217,826,360,000 (Enigma Machine).

http://www.bilibili.com/video/av2883992/. 09 分 52 秒

然而，看起来如此安全的恩格玛机，在剑桥大学的年轻数学家图灵（Alan Turing）[51]面前也并非想象的那样牢不可破。图灵一直从事二进制数学和可编程计算机理论方面的研究。接到英国密码分析中心的招聘后，图灵从波兰的「炸弹」电子计算机入手，分析恩格玛机新增的转子和插接板设置。经过艰苦的努力，图灵利用了恩格玛机的一些瑕疵，设计并实现了新的「炸弹」（Bombe）计算机，用于破解恩格玛机。「炸弹」的破解速度非常快，效率高的时候，「炸弹」可以在 1 小时以内解密所有密文。果然，机器的密码还是要用机器来破解。

图 15：图灵设计并实现「炸弹」的重制机器

http://www.cryptomuseum.com/crypto/bombe/img/bombe_replica_full.jpg

「炸弹」中的很多思想都可以看作现代计算机的雏形。图灵为现代计算机的诞生做出了突出贡献。为了纪念图灵，人们设立「图灵奖」[52]，奖励为计算机做出贡献的计算机科学家们。

现在的安全加密算法

密码学家和计算机科学家们继续为安全加密算法的设计做出不懈的努力。他们设计了多种安全可靠的加密算法。比较著名的有 1977 年 1 月由美国国家标准局公布的数据加密标准（Data Encryption Standard，DES）。DES 的出现是现代密码学的标志之一，意味着密码学已经上升为数学和计算机科学的交叉学科。DES 被使用了将近 20 年。为了适应现今的安全要求，1998 年密码学家们推出了一系列替代 DES 的新型算法，如 MARS、RC6、Sperpent、Twofish 等。2000 年 10 月 2 日，美国国家标准和技术协会（National Institution of Standards and Technology，NIST）宣布，经过 3 年多的筛选和测评，比利时密码学家Daemen 和 Rijmen 共同设计的 Rijndael 加密算法成为了新的加密标准。这个新的算法被命名为高级加密标准（Advanced Encryption Standard，AES）[53]。现今，AES 已经被广泛使用。密码学家们仍然没有发现AES的致命缺陷。我们可以认为，到现在为止，AES 仍然是安全的加密算法。

图 16：比利时密码学家 Daemen 与 Rijmen

https://geek.hellyer.kiwi/files/2013/12/aes-devs.jpg

公钥密码学的诞生

加密的困境：密钥分发问题

虽然密码学家们设计了多种安全的加密算法，但这些加密算法在使用之前都要解决一个很麻烦的问题：密钥分发问题。

以门锁为例。我们几乎每天都要和门锁与钥匙打交道。安全的门锁大概有什么样的要求呢？简单地说有这么几条：

•  门锁要非常坚固，如果没有钥匙的话，任何人都不能够打开门锁；

•  钥匙必须足够复杂，除非得到了原始的开锁钥匙，否则钥匙非常难以复制；

•  当然了，门本身也必须足够结实。

对应来看的话，加密算法也需要具有这些特征：

•  加密算法要足够安全，没有密钥的攻击者无法从密文中解读出任何有价值的信息；

•  密钥必须足够复杂，足够长，哪怕密钥有一个数设置错误，都无法正确解密；

•  当然了，使用加密算法时也需要足够小心，不要有操作上的失误。

按照这样的安全要求，人们制作了很多安全的门锁，对应的钥匙也变得越来越复杂。但是，这些门锁都有一个共同的问题：锁门的时候必须用钥匙锁！在实际生活中这是个好事：如果不用钥匙锁，我把门直接撞上而自己又没带钥匙，岂不是我本人也进不去了。如果只是我自己或者家人锁门的话还好。可是，如果我希望别人帮我锁门的话，事情就比较麻烦了，比如：

•  亲戚来我家做客，但我临时有事要出门，不知道几点回来。难道我要请亲戚看家，等我回来再离开吗？最好的方法是亲戚离开我家的时候，帮我把门撞上就好了。

•  我新买了一套房子，需要装修队装修。装修过程中，我可以每天早上来新家把门打开，允许装修队随时进入。但是，如果今天的装修工作结束了，装修队需要等我晚上回来把门锁上才能走？

人类的智慧是无穷的。为了解决上面的问题，人类设计了能撞门的锁。锁门的时候，我们就不再需要钥匙了，直接把门撞上就可以离开。只要把门撞好，没有钥匙同样也打不开门锁。

图 17：对称加密体制简析

在双方进行通信时，我们也会遇到这样的问题。通信就好像双方互相之间发送密码保险箱一样：发送方把信息放在保险箱中，用钥匙将保险箱锁住，这就是加密过程；接收方用相同的钥匙打开保险箱，得到放置在内部的信息，这就是解密过程，整个过程如图 17 所示。在公钥密码学诞生之前，密码学家们所设计的所有加密算法都遵从了上面的原理。由于加密解密所使用的密钥相同的，看起来就像是镜子里面对称的一样，因此密码学上把这类加密方法称为「对称加密」（Symmetric Encryption）。

然而，我们遇到了一个很棘手的问题：双方在通信之前如何得到同一个保险箱的同一个钥匙呢？仅有的办法是两个人一同购买一个保险箱，每个人拿着一把钥匙。然而，在实际通信过程中绝大多数情况下双方很难见面，怎么办呢？第二次世界大战期间，德军解决的方法是设立通信兵。通信兵每个月集合一次，集合时下发这个月所使用的恩格玛机密钥。图 18 就是德军所使用的密钥表。表格中从左到右依次为：转子的排列顺序、转子的初始位置、插接板的连接方法、为进一步增加安全性所使用的附加密码。

图 18：德军所使用的恩格玛机密钥表

http://www.cryptomuseum.com/crypto/enigma/ukwd/img/lw_key_2744_full.jpg

那么，在密码学上能不能找到一种类似撞门的方法：设计一种加密算法，使得加密明文时发送方不需要知道密钥，只使用一个接收方公开的信息实现加密；解密时，接收方仍然可以使用自己的密钥进行解密，而其他人却无法从密文中获取任何有价值的信息呢？也就是实现如图 19 所示的过程。这时候，加密和解密所使用的密钥就不一样了，密钥不再对称。密码学上把这种加密方法称为「非对称加密」（Asymmetric Encryption）。由于加密时，发送方虽然也使用了密钥，但这个密钥是接收方向全世界公开的，因此这种加密方法又被称为「公钥加密」（Public Key Encryption）。所有利用公钥思想实现的密码学被称为「公钥密码学」（Public Key Cryptography）。在 1976 年之前，公钥密码学的想法被视为天方夜谭。但在 1976 年，密码学的天才们提出了并实现了这个想法。而这个想法的实现就用到了前面讲到的质数性质和困难问题。

图 19：非对称加密体制简析

公钥密码学的思想：利用离散对数困难问题

讲到这里，我需要隆重推出一位为公钥密码学做出了突出贡献，但却鲜为人知的天才密码学家 Ralph Merkle[54]。Merkle 于 1970 年开始在伯克利大学研究计算机科学，并于 1974 年和 1977 年分别在伯克利大学获得了学士和硕士学位。Merkle 是个天才，在所有密码学家们还在深入研究对称加密体制等传统密码学时，Merkle 于 1974 年就提出了公钥密码学的思想：

是否可以在不安全的通信信道中建立安全通信机制？

然而，Merkle 的思想遭到了伯克利大学老师的严重反对。Merkle 在撰写博士研究计划时提出了两个项目，第 1 个项目就是公钥密码学的思想。然而，在浏览了 Merkle 所提出的思想后，伯克利大学老师对其的评论是：

第二个项目看起来更合理一些，或许是因为你所描述第一个项目实在是太糟糕了(ii)。

图 20：伯克利大学老师对Merkle 项目的评价，红色方框里为具体内容

http://119.90.25.33/www.merkle.com/1974/FirstCS244projectProposal.pdf

不幸的是，不光伯克利大学的老师们不认可 Merkle 的思想，当时世界上几乎所有的密码学家们也都不认同这一思想。Merkle 在 1975 年投稿至著名国际期刊「Communications of the ACM」的论文「不可信信道中实现安全通信」（Secure Communications over Insecure Channels）也被无情的拒稿。图 21 是「Communications of the ACM」的编辑给出的论文最终结论。

由于研究成果不被认可，Merkle 无法在伯克利取得博士学位。就在绝望的时候，他了解到斯坦福大学的两位老师 Diffie 与 Hellman 也在朦胧地考虑公钥密码学的思想。于是，Merkle 便前往斯坦福大学，成为 Hellman 的博士生，并于 Diffie 老师合作，继续践行自己的想法。

1976 年，信息理论的著名国际期刊「IEEE Transactions on Information Theory」向Diffie 与Hellman 发出邀请，希望他们撰写一篇论文，介绍密码学的最新研究进展。当时 Merkle 还是 Hellman 的博士生，这样著名的期刊当然不会邀请Merkle 撰写文章了。于是，Diffie 与 Hellman 作为作者，受邀在这一著名的国际期刊上发表了划时代的论文「New Directions in Cryptography」[55]。在论文中，Diffie 与 Hellman 首次公开了一种方法，使得通信双方可以通过不可信的信道分享出一个相同的密钥。Diffie 与 Hellman 因此成为了第一个公开提出公钥密码学思想的学者。后来，人们把这个协商密钥的方法称为 Diffie-Hellman 密钥协商协议。在论文发表 30 年后的 2015 年，Diffie 与 Hellman 因这一杰出贡献获得了图灵奖。

图 21：1975 年Communications of the ACM发送给Merkle 的拒稿信

http://119.90.25.22/www.merkle.com/1974/RejectionLetter.pdf

这样一个划时代的成果，其算法的构造会及其复杂吧？实际上，这个算法之简单，只要大家阅读了前面所介绍的模质数 p 下的运算，就可以很好地理解Diffie-Hellman 密钥协商协议。

图 22：（从右至左）Diffie、Hellman 与 Merkle 在一起工作

https://pic3.zhimg.com/e4d9cb99b4c9d5cc05e4744c1002b40e_r.png

图 23 给出了密钥协商协议的具体流程。假定 Alice 和 Bob 要在不安全的信道上共享一个密钥。所谓不安全的信道，是指攻击者可以看到 Alice 与 Bob 通信的全部内容。Diffie-Hellman 密钥协商协议流程如下：

1. Alice 和 Bob 约定一个很大的质数 p，以及模 p 下的生成元 g；

2. Alice 选择一个小于 p 的秘密随机数 a，计算 A=ga(mod p)，并把 A 发送给 Bob；

3. Bob 选择一个小于 p 的秘密随机数 b，计算 B=gb(mod p)，并把 B 发送给 Alice；

4. Alice 收到 B 后，计算 Key=Ba=(gb)a=gab(mod p)

5. Bob 收到 A 后，计算 Key=Ab=(ga)b=gab(mod p)

整个过程中，Alice 向 Bob 发送了 A，Bob 向 Alice 发送了 B。所有计算都可以快速完成。

这个协议神奇的地方在于，A、B、p、g 都可以通过不安全的信道发送。就算攻击者看到了 A、B、p、g，他也无法知道 Key 的值是多少。为什么呢？直观来看，想要得到 Key 的值，攻击者至少需要根据 A、g 和质数 p 求 a=log gA ，或者根据B、g 和质数 p 求 b=log gB。但这就要解决模质数 p 下的离散对数问题。前面已经讲过，离散对数问题是一个非常困难的问题，并没有方法可以快速解决。因此，只要 Alice 和 Bob 选择了足够大的 p，攻击者就算看到了 Alice 和 Bob 发送的全部信息，对于获取密钥 Key 也无能为力。实际上，已知 p、g、A=ga(mod p)、B=gb(mod p)，求 Key=gab(mod p) 的问题，称为计算 Diffie-Hellman 问题（Computational Diffie-Hellman 问题），这个问题几乎和离散对数问题一样困难。

图 23：Diffie-Hellman 密钥协商协议

随着 1976 年 Diffie 与 Hellman 这篇划时代论文的公布，密码学家们才真正认识到公钥密码学的来临。他们对 Merkle 的判断出现了错误。因此，在 1978 年，「Communications of the ACM」弥补了 1975 年所犯下的错误，正式接收了 Merkle 的论文「Secure Communications over Insecure Channels」[56]。

Diffie-Hellman 密钥协商协议现在仍然被认为是安全的。我们在浏览互联网时，Diffie-Hellman 密钥协商协议就在默默地保护着我们。本文中的大多数信息参考来源：维基百科网站，就在使用 Diffie-Hellman 密钥协商协议的变种，基于椭圆曲线的 Diffie-Hellman 密钥协商协议与我们的浏览器建立通信。图 24 是 2016 年 8 月 5 日中文维基百科网站的安全信息。「公钥参数」一栏写的是「ECDH_P256」。EC 就是椭圆曲线英文「Elliptic Curve」的缩写，DH 就是 Diffie-Hellman 的缩写，后面的 P256 指的是使用了模数为 256 为质数 P 的椭圆曲线。

图 24：维基百科的证书信息

https://zh.wikipedia.org/wiki/Wikipedia:%E9%A6%96%E9%A1%B5. Accessed 2016.08.05

公钥密码学的诞生：利用整数分解困难问题

Diffie-Hellman 密钥协商协议虽然很不错，但它在功能上有一个严重的缺失：人们只能用这个协议共享一个密钥，但是不能直接用这个协议实现信息的加密。这个问题在很长时间内一直困扰着 Diffie、Hellman 与 Merkle。实际上，他们只需要再突破一点点就能达到目的了。然而，在科学研究中，哪怕是这样一点点的突破都非常的困难。直到 1985 年，密码学家 ElGamal 才改进了 Diffie-Hellman 密钥协商协议，使它可以实现信息的加密。这个加密方案被称为 ElGamal 加密方案[57]。

那么，如何利用困难问题实现公钥加密呢？1976 年，来自麻省理工学院的三位年轻密码学家 Ron Rivest、Adi Shamir、Leonard Adleman 提出了一种模数为合数 n 下的算法，彻底实现了公钥加密的功能[58]。这个算法后来就以他们三个人的形式开头字母组成，称为 RSA 算法。

图 25：Rivest、Shamir 与Adleman

http://www.boiledbeans.net/wp-content/uploads/2007/10/3d454f411f112cb3df7e62ed5907b4a0.jpg

RSA 算法拥有三个步骤：密钥生成、加密、解密。Alice 执行密钥生成步骤，得到自己的公钥和私钥，并把公钥向外界公开。发送方 Bob 将利用 Alice 的公钥对明文进行加密，并把加密结果发送给 Alice。只有拥有公钥所对应私钥的 Alice 才能执行解密步骤，正确恢复出明文。RSA算法的具体过程如图 26 所示：

•  密钥生成：Alice 选择两个大质数 p、q，计算 n=p×q。随后，Alice 选择一个与欧拉函数 φ(n)=(p−1)(q−1) 互质的数 e，并计算 d=e⁻¹mod(p−1)(q−1)。前面我们知道，只有当 e 和 (p−1)(q−1) 互质，Alice 才能找到满足条件的 d。Alice 的私钥为 d，公钥为 (n, e)。

•  加密：Bob 想要给 Alice 发送明文 m，Bob 简单地计算 C=memod n，就得到了密文。

•  解密：Alice 收到密文C后，计算 Cd=(me)d=med=me×e⁻¹=m¹=m(mod n)。

图 26：RSA算法

由于Alice 知道 n 的质因数 p 和 q，她可以很容易计算得到 (p−1)(q−1)，这样就可以求得私钥 d 了。然而，攻击者并不知道 n 的质因子，因此也就无法得到 (p−1)(q−1)。由于攻击者无法从公钥 e 中求得 d，因此攻击者无法从密文中解密出明文 m。由于对于比较大的 n 来说，n 整数分解是一个公认困难问题，因此攻击者对密文就无能为力了。

讲到这里有的朋友们会提出这样一个疑问：攻击者只能通过对 n 求整数分解，才能得到 d，或者才能得到 m 吗？是否有什么投机取巧的方法？很遗憾，经过 30 多年密码学家们的研究，只要各个数的选择得当，求 m 与 n 的整数分解几乎是一样困难的[59]。

RSA 算法构造即为简单，也很容易理解，只需要知道质数、合数、同余、指数运算、互质等基本的数学概念，结合一定的要求即可正确使用。与此同时，通过调换公钥和私钥的位置，RSA 还可以实现公钥密码学中的另一个功能：「数字签名」。现今，RSA 依然是被广泛使用的公钥加密与数字签名方案。我们常用的知乎网站就使用了 2048 位的 RSA。图 27 为知乎网站的安全信息。「公钥」一栏写的是「RSA (2048Bits)」，表示该网站使用了RSA算法，其合数 n 的程度为二进制 2048 位。

图 27：知乎的证书信息

https://www.zhihu.com. Accessed 2016.08.05

公钥密码学的未来

1994 年，麻省理工学院的教授 Peter Shor[60]宣称他找到了一个算法，可以快速解决整数分解问题，这个算法被称为 Shor 算法[61]。全世界的数学家们和密码学家们开始时对此并不太感兴趣，因为全世界几乎每隔一段时间就会有某个人站出来表示自己解决的整数分解问题，但是所有的算法都有严重的问题。然而，经过深入的检查后，全世界的数学家们发现，Peter Shor 所提出的算法没有任何问题，确实能快速解决整数分解问题[62]。唯一的遗憾是，他的算法在普通计算机上无法实现，而是需要在还不存在的「量子计算机」上实现。后续的研究工作表明，Shor 所提出的算法不仅可以解决整数分解问题，还可以经过修改后解决离散对数问题。如果在未来人类真的研制出了量子计算机，那么 Diffie-Hellman 密钥协商协议、RSA 算法，以及后续提出的多种公钥加密算法将都将变得不安全。

在 1994 年，就算是当时的超级计算机也是体积巨大、计算缓慢，量子计算机更是痴人说梦了。然而，20 多年后的今天，量子计算机正逐渐走进了人类的视野。量子计算机将为人类带来更强的计算能力。然而，它的到来真的会使得公钥密码学再一次坠入深渊吗？

我们还有希望。为了让密码学迎接量子计算机的挑战，2016 年 7 月 7 日，谷歌公司宣布将发起为期 2 年的研究，将抗量子计算攻击的新型公钥加密算法「新希望算法」（New Hope）[63]应用于谷歌的 Chrome 浏览器[64]。新希望算法中同样出现了质数的影子，只不过质数的使用方法变得更加复杂。现在，后量子时代的密码学正得到蓬勃的发展。公钥密码学将要走向何方？质数能否继续保护互联网时代的信息安全呢？我们拭目以待。

(ii) 原文为：Project 2 looks more reasonable, maybe because your describing Project 1 is huddled terribly.参见图 20。

作者说

我是刘巍然，现为北京航空航天大学电子信息工程学院的博士研究生。我的研究方向是公钥密码学及其在大数据安全存储中的应用。密码学是数学与计算机科学的交叉学科，神秘而又充满乐趣。从某种程度上讲，密码学揭示了计算机解决问题的极限。我认为，这与人类不断接近其自身认知极限的宏大目标有着异曲同工之妙。

这次的电子书对我是一个全新的挑战。我从「公钥密码学」回到了「数论」，聚焦在「质数」这样一个我们小学时代就学习过的基本数学概念。数学家们发现了质数的哪些性质？这些性质又在密码学中得到了哪些应用？我希望用这本书来带领大家回顾人类历史上天才们灵光一闪的瞬间。

如果你对密码学（尤其是公钥密码学）感兴趣，欢迎来到知乎与我交流，我的知乎主页是：https://www.zhihu.com/people/liu-wei-ran-8-34。

致谢

在本书的最后，我想真诚感谢为本书的撰写和在线发表做出贡献的朋友们。

非常感谢知乎为我提供了这样一个宝贵的机会。相信知乎平台对回答者们的尊重和支持将为知乎带来更多优质的答案、专栏文章和电子书。

非常感谢我的女友李雯大人对我撰写电子书的大力支持。我比较喜欢在晚上和深夜写东西，较长时间的撰写难免会冷落了大人，特别是在撰写过程中她还患了重感冒，身体一度很虚弱。然而，大人给予我极大地宽容和鼓励，这让我感激不尽。什么都不说了，未来看我表现！

特别感谢我的学妹金歌同学帮助我翻译欧拉给哥德巴赫猜想的回信。金歌同学现在在德国留学，而欧拉的回信似乎是用德语撰写的，因此我就询问金歌同学，是否能帮助我简单翻译一下。没想到，欧拉的回信用的是古德语，里面掺杂了拉丁语，这为翻译带来了很大的困难。金歌同学又是查字典又是问其他德国人，最终帮助我完成了翻译，辛苦了！

感谢信息安全界的很多老师和朋友，以及知乎密码学交流群的朋友们对本书的初稿提出了很多宝贵的意见。

最后，感谢阅读本电子书的各位读者朋友们，希望我的文字能为你带来快乐。

参考文献

[1] Zhang, Y.: Bounded Gaps between Primes. Annals of Mathematics, 2014, 179(3): 1121-1174.

[2] Ormond, J.: Cryptographic Pioneers Receive an ACM A.M. Turing Award. https://www.acm.org/awards/2015-turing. Online, accessed 2016-08-01.

[3] Diffie, W., Hellman, M. New Directions in Cryptography. IEEE Transactions on Information Theory, 1976, 22(6): 644-654.

[4] (美)Kenneth, H. R.著. 袁崇义, 屈婉玲等译. 离散数学及其应用（原书第五版）. 北京: 机械工业出版社, 2007.06.

[5] 覃中平, 张焕国等. 信息安全数学基础. 北京: 清华大学出版社, 2006.08.

[6] 刘建伟, 王育民. 网络安全——技术与实践（第 2 版）. 北京: 清华大学出版社, 2011.06.

[7] (美)Lunde P.著. 刘建伟, 王琼译. 密码的奥秘. 北京: 电子工业出版社, 2015.03.

[8] 维基百科. 哥德巴赫猜想. https://zh.wikipedia.org/wiki/%E5%93%A5%E5%BE%B7%E5%B7%B4%E8%B5%AB%E7%8C%9C%E6%83%B3. Online, accessed 2016.08.02.

[9] Goldbach C. 1742, 第 43 号信件, 手稿影印本. https://math.dartmouth.edu/~euler/correspondence/letters/OO0765.pdf. Online, accessed 2016.08.02.

[10] Euler L. 1742, 第 44 号信件, 手稿影印本. https://math.dartmouth.edu/~euler/correspondence/letters/OO0766.pdf. Online, accessed 2016.08.02.

[11] 潘承洞, 潘承彪. 哥德巴赫猜想（第二版）. 北京: 科学出版社, 2011.11.

[12] 维基百科. 弱哥德巴赫猜想. https://zh.wikipedia.org/wiki/%E5%BC%B1%E5%93%A5%E5%BE%B7%E5%B7%B4%E8%B5%AB%E7%8C%9C%E6%83%B3. Online, accessed 2016.08.02.

[13] 维基百科. 希尔伯特的 23 个问题. https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%9A%8423%E4%B8%AA%E9%97%AE%E9%A2%98. Online, accessed 2016.08.02.

[14] Deshouillers, J. M., Effinger, G., Te Riele, H., Zinoviev, D. A Complete Vinogradov 3-Primes Theorem under the Riemann Hypothesis. Electronic Research Announcements of the American Mathematical Society 3, 1997, 15: 99-104.

[15] Kaniecki, L. On Šnirelman's constant under the Riemann hypothesis. Acta Arith, 1995, 72: 361-374.

[16] Tao, T. Every Odd Number Greater than 1 is the Sum of at Most Five Primes. Mathematics of Computation, 2014, 83(286): 997-1038.

[17] Wang Y. The Goldbach Conjecture. Second Edition. World Scientific Publishing Company, 2002.

[18] Helfgott, H. A. Minor Arcs for Goldbach’s Problem. arXiv Preprint arXiv: 1205.5252, 2012. Available at: http://arxiv.org/abs/1205.5252.

[19] Helfgott, H. A. Major Arcs for Goldbach’s Problem. arXiv Preprint arXiv: 1305.2897, 2013. Available at: http://arxiv.org/abs/1305.2897.

[20] Chen, J. On the Representation of a Large Even Number as the Sum of a Prime and the Product of at most Two Primes. Scientia Sinica, 1973, 16(2): 157-176.

[21] 维基百科. 孪生质数猜想. https://zh.wikipedia.org/wiki/%E5%AD%AA%E7%94%9F%E7%B4%A0%E6%95%B0%E7%8C%9C%E6%83%B3. Online, accessed 2016.08.02.

[22] McKee, M. First Proof that Infinitely Many Prime Numbers Come in Pairs. Nature International Weekly Journal of Science, 2013.05.14. http://www.nature.com/news/first-proof-that-infinitely-many-prime-numbers-come-in-pairs-1.12989. Online, accessed 2016.08.02.

[23] Tao T. Polymath Proposal: Bounded Gaps between Primes. The PloyMath Blog, 2013.06.04. https://polymathprojects.org/2013/06/04/polymath-proposal-bounded-gaps-between-primes. Online, accessed 2016.08.01.

[24] Wlotman, G. Great Internet Mersenne Prime Search. http://www.mersenne.org. Online, accessed 2016.08.02.

[25] Woltman, G. GIMPS Milestones Report. http://www.mersenne.org/report_milestones. Online, accessed 2016.08.03.

[26] Wiles, A. Modular Elliptic Curves and Fermat’s Last Theorem. Annals of Mathematics, 1995, 141(3): 443-551.

[27] Solovay, R. M., Strassen, V. A Fast Mote-Carlo Test for Primality. SIAM Journal on Computing, 1977, 6(1): 84-85.

[28] Miller, G. L. Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System Sciences, 1976, 13(3): 300-317.

[29] Rabin, M. O. Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 1980, 12(1): 128-138.

[30] 刘慈欣. 三体. 重庆: 重庆出版社, 2008.01.

[31] Wikipedia. Integer factorization. https://en.wikipedia.org/wiki/Integer_factorization. Online, accessed 2016.08.04.

[32] Wikipedia. RSA Security. https://en.wikipedia.org/wiki/RSA_Security. Online, accessed 2016.08.04.

[33] Wikipedia. RSA Factoring Challenge. https://en.wikipedia.org/wiki/RSA_Factoring_Challenge. Online, accessed 2016.08.04.

[34] RSA Laboratories. The RSA Factoring Challenge. http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge-faq.htm. Online, retrieved on 2013.11.09, accessed 2016.08.04.

[35] Wikipedia. Discrete Logarithm Records. https://en.wikipedia.org/wiki/Discrete_logarithm_records. Online, accessed 2016.08.04.

[36] Joux, A., Lercier, R. Discrete Logarithms in GF(p) – 130 digits, 2005. Announcement available at the NMBRTHRY archives, item 002869.

[37] Kleinjung, T. Discrete Logarithms in GF(p) – 160 digits, 2007. Announcement available at the NMBRTHRY archives. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0702&L=NMBRTHRY&P=R45&D=0&I=-3&T=0. Online, accessed 2016.08.04.

[38] Bouvier, C., Gaudry, P., Imbert, L., Thomé. Discrete Logarithms in GF(p) – 180 digits. Announcement available at the NMBRTHRY archives. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1406&L=NMBRTHRY&F=&S=&P=3161. Online, accessed 2016.08.04.

[39] Wikipedia. Grille (Cryptography). https://en.wikipedia.org/wiki/Grille_(cryptography). Online, accessed 2016.08.04.

[40] 维基百科. 猪圈密码. https://zh.wikipedia.org/wiki/%E8%B1%AC%E5%9C%88%E5%AF%86%E7%A2%BC. Online, accessed 2016.08.04.

[41] Wikipedia. Leon Battista Alberti. https://en.wikipedia.org/wiki/Leon_Battista_Alberti. Online, accessed 2016.08.04.

[42] Wikipedia. Giovan Battista Bellaso. https://en.wikipedia.org/wiki/Giovan_Battista_Bellaso. Online, accessed 2016.08.04.

[43] Wikipedia. Blaise de Vigenère. https://en.wikipedia.org/wiki/Blaise_de_Vigen%C3%A8re. Online, accessed 2016.08.04.

[44] Wikipedia. Vigenère Cipher. https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher. Online, accessed 2016.08.04.

[45] Wikipedia. Friedrich Kasiski. https://en.wikipedia.org/wiki/Friedrich_Kasiski. Online, accessed 2016.08.04.

[46] Wikipedia. Kasiski Examination. https://en.wikipedia.org/wiki/Kasiski_examination. Online, accessed 2016.08.04.

[47] Wikipedia. Charles Babbage. https://en.wikipedia.org/wiki/Charles_Babbage. Online, accessed 2016.08.04.

[48] Wikipedia. Typex. https://en.wikipedia.org/wiki/Typex. Online, accessed 2016.08.05.

[49] Wikipedia. SIGABA. https://en.wikipedia.org/wiki/SIGABA. Online, accessed 2016.08.05.

[50] Wikipedia. Engima Machine. https://en.wikipedia.org/wiki/Enigma_machine. Online, accessed 2016.08.05.

[51] Wikipedia. Alan Turing. https://en.wikipedia.org/wiki/Alan_Turing. Online, accessed 2016.08.05.

[52] ACM. A.M. Turing Award. http://amturing.acm.org. Online, accessed 2016.08.05.

[53] Daemen, J., Rijmen V. The Design of Rijndael: AES – the Advanced Encryption Standard. Springer Science & Business Media, 2013.

[54] Wikipedia. Ralph Merkle. https://en.wikipedia.org/wiki/Ralph_Merkle. Online, accessed 2016.08.05.

[55] Diffie, W., Hellman, M.E. New Directions in Cryptography. IEEE Transactions on Information Theory, 1976, 22(6): 644-654.

[56] Merkle, R. Secure Communications over Insecure Channels. Communications of the ACM, 1978, 21(4): 294-299.

[57] ElGamal, T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, 1985, 31(4): 469-472.

[58] Rivest, R., Shamir, A., Adleman, L. Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1977, 21(2): 120-126.

[59] Aggarwal, D., Maurer, U. Breaking RSA Generally is Equivalent to Factoring. EUROCRYPT 2009, pp. 36-53.

[60] Wikipedia. Peter Shor. https://en.wikipedia.org/wiki/Peter_Shor. Online, accessed 2016.08.05.

[61] Wikipedia. Shor’s Algorithm. https://en.wikipedia.org/wiki/Shor%27s_algorithm. Online, accessed 2016.08.05.

[62] Beckman, D., Chari, A. N., Devabhaktuni, S., Preskill, J. Efficient Networks for Quantum Factoring. Physical Review A, 1996, 54(2): 1034.

[63] Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P. Post-Quantum Key Exchange – A New Hope. IACR ePrint Achieve, 2015/1092. Available at https://eprint.iacr.org/2015/1092.pdf.

[64] Statt, N. Google is Working to Safeguard Chrome from Quantum Computers. The Verge. http://www.theverge.com/2016/7/7/12120280/google-chrome-canary-quantum-computing-encryption-new-hope. Online, accessed 2016.08.05.