公钥密码学的数学基础(第2版)

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

第二版前言
第一版序
第一版前言
第1章整除1
1.1整除的概念1
1.2优选公因子与最小公倍数5
1.3Euclid算法10
1.4求解一次不定方程——Euclid算法应用之一13
1.5整数的素分解14
1.6使用SageMath进行整除相关的计算20
习题121
第2章同余23
2.1同余的基本概念和基本性质23
2.2剩余类与剩余系26
2.3Euler定理31
2.4Wilson定理34
2.5使用SageMath进行同余相关的计算37
习题238
第3章同余方程40
3.1一元高次同余方程的概念40
3.2一次同余方程43
3.3一次同余方程组与孙子定理44
3.4一般同余方程47
3.5二次剩余49
3.6Legendre符号与acobi符号52
3.7使用SageMath求解同余方程59
习题359
第4章指数与原根61
4.1指数及其性质61
4.2原根及其性质64
4.3指标、既约剩余系的构造67
4.4n次剩余72
4.5使用SageMath进行指数与原根相关的计算75
习题476
第5章素数分布的初等结果78
5.1素数的基本性质与分布的主要结果介绍78
5.2Euler恒等式的证明81
5.3弱形式素数定理的证明83
5.4素数定理的等价命题90
5.5使用SageMath进行素数分布相关的计算93
习题594
第6章简单连分数95
6.1简单连分数及其基本性质95
6.2实数的简单连分数表示98
6.3连分数在密码学中的应用——对RSA算法的低解密指数攻击103
6.4使用SageMath进行简单连分数相关的计算104
习题6105
第7章近世代数基本概念106
7.1映射106
7.2代数运算109
7.3带有运算集合之间的同态映射与同构映射111
7.4等价关系与分类112
习题7113
第8章群论114
8.1群的定义114
8.2循环群116
8.3子群、子群的陪集117
8.4同态基本定理121
8.5有限群的实例124
8.6使用SageMath进行群论相关的计算127
习题8128
第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
习题9151
第10章公钥密码学中的数学问题152
10.1时间估计与算法复杂性152
10.2素检测158
10.3分解因子问题160
10.4RSA问题与强RSA问题161
10.5二次剩余162
10.6离散对数问题164
10.7使用SageMath求解公钥密码学中的数学问题166
习题10167
第11章格的基本知识168
11.1基本概念168
11.2格相关的计算问题169
11.3格基约化算法171
11.4LLL算法应用173
11.5使用SageMath进行格相关的计算179
习题11179
参考文献181