本书介绍了群、环、域、数论、组合论、移位寄存器序列、计算复杂性、信息论与数理逻辑等诸多与信息安全相关联的数学基础内容。本书以大量的例题说明数学的抽象概念对信息安全中的诸多对象的本质刻画。本书内容全面系统，包括信息安全领域最主要的数学知识，并与信息安全的应用结合十分紧密，这是目前其他书籍所不具备的显著特点。

    本书可作为信息安全领域的研究生与大学生的相关课程的教材，也可作为信息安全领域的工程技术人员的参考书。

21世纪是信息时代，信息已成为社会发展的重要战略资源，社会的信息化已成为当今世界发展的潮流和核心，而信息安全在信息社会中将扮演极为重要的角色，它直接关系到国家安全、企业经营和人们的日常生活。 随着信息安全产业的快速发展，国家对信息安全人才的需求量不断增加，但目前信息安全人才极度匮乏，远远不能满足金融、商业、公安、军事和政府等部门的需求。要解决供需矛盾，必须加快信息安全人才的培养，以满足社会的需求。为此，教育部继2001年批准在武汉大学开设信息安全本科专业之后，又批准了多所高等院校设立信息安全本科专业，而且许多高校和科研院所已设立了信息安全方向的具有硕士和博士学位授予权的学科点。

信息安全是计算机、通信工程、数学等领域的交叉学科，对于这一新兴学科的培养模式和课程设置，各高校普遍缺乏经验，因此中国计算机学会教育专业委员会和清华大学出版社联合主办了“信息安全专业教育教学研讨会”等一系列研讨活动，并成立了《高等院校信息安全专业系列教材》编审委员会，由我国信息安全领域著名专家何德全院士担任名誉主编，著名学者肖国镇教授担任编委会主任，共同指导《高等院校信息安全专业系列教材》的编写工作。编委会本着研究先行的指导原则，认真研讨国内外高等院校信息安全专业的教学体系和课程设置，进行了大量前瞻性的研究工作，而且这种研究工作将随着我国信息安全专业的发展不断深入。经过编委会全体委员及相关专家的推荐和审定，确定了编写教材的作者，这些作者绝大多数都是既在本专业领域有深厚的学术造诣，又在教学第一线有丰富教学经验的学者、专家。

本系列教材是我国第一套专门针对信息安全专业的教材，其特点是：

① 体系完整，结构合理，内容先进。

② 适应面广，能够满足信息安全、计算机、通信工程等相关专业对信息安全领域课程的教材要求。

③ 立体配套，除主教材外，还配有多媒体电子教案、习题与实验指导等。

④ 版本更新及时，紧跟科学技术的新发展。

为了保证出版质量，我们坚持宁缺毋滥的原则，成熟一本，出版一本，并保持不断更新，力求将我国信息安全领域教育、科研的最新成果和成熟经验反映到教材中来。在全力做好本版教材，满足学生用书的基础上，还经由专家的推荐和审定，遴选了一批国外信息安全领域优秀的教材加入到本系列教材中，以进一步满足大家对外版书的需求。热切期望广大教师和科研工作者加入我们的队伍，同时也欢迎广大读者提出宝贵意见，以便我们对本系列教材的组织、编写与出版工作不断改进，为我国信息安全专业的教材建设与人才培养做出更大的贡献。

21世纪是信息的时代。信息成为社会发展的重要战略资源。信息安全事关国家安全和社会稳定。信息安全已经成为世人关注的社会问题和信息科学领域的热点研究课题。

发展信息安全事业，人才是关键。2001年，武汉大学创建了全国第一个信息安全本科专业。现在，全国已有30多所高校建立了信息安全专业。中国的信息安全人才培养工作进入了蓬勃发展的阶段。

信息安全是计算机、通信、电子、数学、物理、生物、法律、管理、教育等多学科交叉的学科。就技术而言，硬件结构的安全和操作系统的安全是信息系统安全的基础，密码和网络安全等是关键技术。

数学是自然科学的基础，同样也是信息安全学科的基础。本书讲授信息安全领域应用的数学基础知识，是信息安全专业的基础课教材。

本书包含群、环、域、数论、组合论、移位寄存器序列、计算复杂性、信息论与数理逻辑等诸多与信息安全相关联的数学基础内容。本书以大量的例题说明数学的抽象概念对信息安全中的诸多对象的本质刻画。该书可作为信息安全、计算机、通信、电子等领域的研究生与大学生相关课程的教科书，也可作为这些领域的工程技术人员的参考书。 

书中，群与环两章由覃中平编写，域与移位寄存器序列两章由张焕国编写，数论由余启港编写，组合论与计算复杂性由黄竟伟编写，信息论由乔秦宝编写，数理逻辑由肖德琴编写。由覃中平对全书进行统稿。    

本书内容全面系统，包括信息安全领域最主要的数学知识，并与信息安全的应用结合十分紧密，这是目前其他书籍所不具备的显著特点。

本书是作者长期从事信息安全教学和科研的基础上写成的。其研究工作得到国家自然科学基金项目（90104005，66973034，60373087）、国家863计划项目（2002AA141051）、国家密码发展基金和教育部博士点基金项目（20020486046）的资助。其大部分内容在武汉大学和华中科技大学进行过教学实践。

由于作者水平所限，书中难免会有不妥和错误之处。对此，作者恳请读者批评指正，并于此先致感谢之意。

作者于武汉2006年6月

第1章群1

1.1群的定义1

1.2群的性质4

1.3群的陪集分解6

1.4正规子群、商群、群同态、群同构7

1.5置换群9

习题11

第2章环12

2.1环的定义12

2.2理想、商环13

2.3多项式环15

2.4商域16

习题17

第3章域18

3.1域的概念18

3.1.1域的定义18

3.1.2域的基本性质19

    3.1.3域上的多项式20

3.2有限域的加法特性31

3.3有限域的乘法特性33

3.4最小多项式与本原多项式36

3.4.1最小多项式与本原多项式的概念36

3.4.2有限域上的多项式xn-1的分解38

3.4.3多项式的周期44

3.5有限域的表示和运算46

3.5.1有限域GF(2n)的表示和运算47

3.5.2素域GF(p)的表示和运算50

3.6有限域的结构51

3.6.1数论函数51

3.6.2有限域的结构55

习题59

参考文献60

第4章数论一： 整数的整除和同余61

4.1辗转相除法及其应用61

4.1.1辗转相除法61

4.1.2最大公因数与最小公倍数63

4．1．3一次不定方程64

4．1．4一次同余方程65

4．1．5整数的惟一分解定理68

4.2整数的同余 69

4．2．1剩余系69

4．2．2欧拉函数和欧拉定理70

4．2．3孙子定理和剩余表示73

4.3一般同余方程75

4.4二次同余方程79

4．4．1二次同余方程的化简79

4．4．2二次剩余  80

4．4．3勒让德符号和雅可比符号81

4．4．4二次同余方程的解法87

习题90

参考文献93

94

5.1原根94

5.2阶的计算方法96

5.3原根的计算方法99

5.4素性检验100

5．4．1素数的简单判别法100

5.4．2素数的确定判别法101

5.4．3素数的概率判别法103

习题108

参考文献109

第6章组合论110

6.1排列与组合110

6.2容斥原理114

6.3母函数117

6.3.1母函数的概念117

6.3.2母函数的性质119

6.3.3指数型母函数122

6.4递推关系125

6.5区组设计133

6.5.1拉丁方与正交拉丁方133

6.5.2平衡不完全区组设计136

6.5.3区组设计的构造138

习题140

参考文献141

第7章移位寄存器序列142

7.1移位寄存器和移位寄存器序列的概念142

7.2线性移位寄存器序列152

7.2.1线性移位寄存器的序列空间152

7.2.2线性移位寄存器序列的周期性156

7.2.3m序列161

7.2.4线性移位寄存器的综合168

7.3非线性移位寄存器序列简介174

习题177

参考文献178

第8章计算复杂性179

8.1算法的时间复杂性与算法分析179

8.1.1算法的时间复杂性179

8.1.2时间复杂性的渐进表示181

8.1.3算法分析的例子183

8.2NP完全问题187

8.2.1最优化问题与判定问题188

8.2.2P类问题189

8.2.3NP类问题191

8.2.4NP完全问题194

8.3若干典型的NP完全问题196

习题203

参考文献204

第9章信息论205

9.1保密系统数学模型205

9.2自信息和熵208

9.3互信息212

9.4信源编码216

9.5完善保密性222

9.6惟一解距离224

9.7乘积密码系统226

习题227

参考文献228

第10章数理逻辑基础229

10.1经典命题逻辑229

10.1.1简单命题与复合命题230

10.1.2命题逻辑公式232

10.1.3等值演算235

10.1.4命题公式的范式239

10.1.5命题演算系统240

10.2经典一阶逻辑244

10.2.1一阶逻辑的基本概念244

10.2.2一阶逻辑公式及解释246

10.2.3一阶逻辑的等值演算与前束范式249

10.2.4一阶逻辑的推理理论250

10.3模态逻辑253

10.3.1模态命题逻辑253

10.3.2模态谓词逻辑255

10.3.3时态逻辑256

10.3.4动态逻辑258

10.4逻辑与信息安全258

10.4.1BAN逻辑259

10.4.2Kailar逻辑264

10.4.3时序逻辑268

习题273

参考文献275