公钥密码学的数学基础

本书是根据作者多年的教学经验，在原有讲义的基础上经过修改、补充而成的。书中介绍了公钥密码学涵盖的数论代数基本知识与理论体系：第1章至第6章分别介绍了初等数论基础知识，主要包括同余、剩余类、原根和连分数的基本理论以及在公钥密码学中的应用等；第7章至第9章描述了群、环、域三个基本的代数结构及其性质；第10章介绍了与密码学相关的计算复杂性理论及基本数学算法；第11章简单介绍了格理论及格密码分析的基本方法。

目录

第二版前言

第一版序

第一版前言

第1章 整除 1

1.1 整除的概念 1

1.2 最大公因子与最小公倍数 5

1.3 Euclid算法 10

1.4 求解一次不定方程——Euclid算法应用之一 13

1.5 整数的素分解 14

1.6 使用SageMath进行整除相关的计算 20

习题1 21

第2章 同余 23

2.1 同余的基本概念和基本性质 23

2.2 剩余类与剩余系 26

2.3 Euler定理 31

2.4 Wilson定理 34

2.5 使用SageMath进行同余相关的计算 37

习题2 38

第3章 同余方程 40

3.1 一元高次同余方程的概念 40

3.2 一次同余方程 43

3.3 一次同余方程组与孙子定理 44

3.4 一般同余方程 47

3.5 二次剩余 49

3.6 Legendre符号与acobi符号 52

3.7 使用SageMath求解同余方程 59

习题3 59

第4章 指数与原根 61

4.1 指数及其性质 61

4.2 原根及其性质 64

4.3 指标、既约剩余系的构造 67

4.4 n次剩余 72

4.5 使用SageMath进行指数与原根相关的计算 75

习题4 76

第5章 素数分布的初等结果 78

5.1 素数的基本性质与分布的主要结果介绍 78

5.2 Euler恒等式的证明 81

5.3 弱形式素数定理的证明 83

5.4 素数定理的等价命题 90

5.5 使用SageMath进行素数分布相关的计算 93

习题5 94

第6章 简单连分数 95

6.1 简单连分数及其基本性质 95

6.2 实数的简单连分数表示 98

6.3 连分数在密码学中的应用——对RSA算法的低解密指数攻击 103

6.4 使用SageMath进行简单连分数相关的计算 104

习题6 105

第7章 近世代数基本概念 106

7.1 映射 106

7.2 代数运算 109

7.3 带有运算集合之间的同态映射与同构映射 111

7.4 等价关系与分类 112

习题7 113

第8章 群论 114

8.1 群的定义 114

8.2 循环群 116

8.3 子群、子群的陪集 117

8.4 同态基本定理 121

8.5 有限群的实例 124

8.6 使用SageMath进行群论相关的计算 127

习题8 128

第9章 环与域 129

9.1 环的定义 129

9.2 整环、域、除环 131

9.3 子环、理想、环的同态 135

9.4 孙子定理的一般形式 140

9.5 欧氏环 142

9.6 有限域 144

9.7 商域 145

9.8 使用SageMath进行环与域相关的计算 148

习题9 151

第10章 公钥密码学中的数学问题 152

10.1 时间估计与算法复杂性 152

10.2 素检测 158

10.3 分解因子问题 160

10.4 RSA问题与强RSA问题 161

10.5 二次剩余 162

10.6 离散对数问题 164

10.7 使用SageMath求解公钥密码学中的数学问题 166

习题10 167

第11章 格的基本知识 168

11.1 基本概念 168

11.2 格相关的计算问题 169

11.3 格基约化算法 171

11.4 LLL算法应用 173

11.5 使用SageMath进行格相关的计算 179

习题11 179

参考文献 181

第1章整除

 整除是数论中的基本概念.本章主要介绍与整除相关的一些基本概念及其性=质.这些基本概念如整除、因子、公因子、*小公倍数、分解因子等，早在中学时=期已被大家所熟悉.在这里我们将给出这些概念的严格的数学定义.通过掌握这=些概念的数学定义及相关性质，我们可以进一步解决许多初等数论里与整除相关=的问题.整除理论内容丰富，解决问题方法灵活.它不仅是数论、代数的基础，而=且在密码学中有很广泛的应用，如整数的素分解、Euclid算法求*大公因子等问=题在密码学中都有极其重要的应用.

 1.1整除的概念

 我们用集合Z表示全体整数组成的集合，N表示自然数的全体.下面给出整除的定义.

 定义1.1设a，b∈Z，如果存在q∈Z，使得b=aq，那么，=就说b可被a整除，记作a|b，称b是a的倍数，a是b的因子(也=可称为约数、除数).否则就说b不能被a整除，或a不整除b，记作a.b.

 由定义及乘法的运算规律，立即可得出整除的以下性质：

 定理1.2设a，b，c∈Z，则

 (1)a|b且;

 (2)a|b且对任意的有;

 (3)若m∈Z且，则;

 (4)a|b且;

 (5)若，则.

 证明(1)由于a|b，根据整除的定义知存在q1，使.同样存在q2使得，从而即(2)由知，存在r，s使得.对任意的x，y∈Z有，故.反之显然.

 性质(3)—(5)证明类似，读者可以自己补出证明.

 显然±1，±b是b的因子，我们称其为b的显然因子，其他因子称为b的非显然因子，或真因子.由此我们可引出素元的定义.

 定义1.3设整数.如果p除了显然因子±1，±p外没有其他的因子，那么p就称为素元(常称为素数)，若整数，且a除显然因子外还含有真因子，则称a为合数.

 注一般情况下，素数我们只取正的.

 下面我们介绍几个关于素数的定理.

 定理1.4若a为合数，则a的*小真因子为素数.

 证明由a为合数知a>2.设d为a的*小真因子.若d不为素数，则=存在d的真因子d′，使d′|d，由性质(1)知，与d为*小真因子矛盾.定理=得证.

 定理1.5素数有无穷多个.

 证明假设只有有限个素数，设为p1，p2， ，pk.考虑a=p1p2 pk+1，由=定理1.4知，整除a的*小真因子一定为素数，记为p.由于p为素数，因而p必=等于某个pi，所以p|a，p|p1p2 pk同时成立，从而p|1，这与p是素数矛盾.因此=定理得证.

 将素数从小到大排列，假设pn表示第n个素数，π(x)表示不超过x的素数=个数.虽然我们无法知道pn的确切位置，但是，我们可以得到pn的弱上界估计下面定理仅描述了pn的一个弱上界估计与π(x)的一个弱下界估计.而对于π(x)=更为精确的估计，超出本书的讨论范围，有兴趣的读者可参考文献[23].

 定理1.6将全体素数按从小到大的顺序排列，则第n个素数pn与π(x)分别有以下结论：

 (1);

 (2).

 证明(1)我们用归纳法来证明定理的第一部分成立.当n=1时，命题

 显然成立.假设对于时，命题成立.当n=k+1时，由定理1.4知，由归纳假设.

 于是命题(1)得证.

 (2)对于任意的x.2，必存在唯一的整数n，使得，从而由第一部分结论得定理得证.

 初等数论还有一个*基本的结论：带余除法定理，它是整除的一般情形，也是Euclid算法的基础.

 定理1.7设a，b是两个给定的整数且.那么一定存在唯一的一对整数q与r，满足，其中，r被称为b被a除后的*小非负余数.此外a|b的充要条件是r=0.

 证明唯一性：若还有整数q′与r′满足.

 则有及.由整除的性质立即可得，所以唯一性成立.

 存在性：当a|b时，可取.当