本书系统地介绍了信息安全理论与技术所涉及的数论、代数、椭圆曲线等数学理论基础。全书共分为6 章： 第1 章是预备知识， 介绍了书中后面几章所涉及的基础知识； 第2 章和第3 章是数论基础， 包括整数的因子分解、同余式、原根、二次剩余、数论的应用等内容； 第4 章是代数系统， 包括群、环、域的概念， 一元多项式环和有限域理论初步等内容； 第5 章是椭圆曲线， 包括椭圆曲线的预备知识、椭圆曲线、椭圆曲线上的离散对数等内容； 第6 章是线性反馈移位寄存器， 包括反馈移位寄存器、分圆多项式和本原多项式、ｍ 序列等内容。书中每章末都配有适量习题， 以供学生学习和复习巩固书中所学内容。

本书是高等学校信息安全专业本科生的教材， 也可作为信息科学技术类专业（如计算机科学技术、通信工程和电子科学技术等） 本科生和研究生的教材， 同时， 也可以供从事信息安全和其他信息技术工作的人员参考。

计算机与网络技术的飞速发展和广泛应用， 极大地促进了社会的发展， 也极大地改变了人们的生活和工作方式。与此同时， 信息安全问题也更多地受到关注： 信息安全理论与技术已经成为信息科学与技术中极为重要的研究领域； 信息安全专门人才的培养受到了社会空前的重视。

“信息安全数学基础” 是信息安全专业本科的专业基础课， 对信息安全理论和技术的深入学习具有重要的意义。本书是在南开大学信息安全专业“信息安全数学基础” 课程授课讲义的基础上整理而成的。全书共分为6 章： 第1 章是预备知识， 介绍了书中所涉及的基础知识； 第2 章和第3 章是数论基础， 包括整数的因子分解、同余式、原根、二次剩余和数论的应用等内容； 第4 章是代数系统， 包括群、环、域的概念， 一元多项式环和有限域理论初步等内容； 第5 章是椭圆曲线， 包括椭圆曲线的预备知识、椭圆曲线、椭圆曲线上的离散对数等内容； 第6 章是线性反馈移位寄存器， 包括反馈移位寄存器、分圆多项式和本原多项式、ｍ 序列等内容。书中每章末都配有适量的习题， 供学生在学习和复习巩固书中所学内容时使用。

本书内容的选取， 我们参照了“高等学校信息安全专业指导性专业规范（第二版）”中对“信息安全数学基础” 相关教学内容和要求的阐述； 并将多年来积累的实际教学经验融入其中， 力求知识系统化、较好地覆盖信息安全领域所涉及的数学基础知识。对书中内容所涉及的基础预备知识做了简明扼要的介绍； 书中所涉及的数学结论都给出了详细的证明； 习题的配置着力于帮助学生巩固所学的内容和能力拓展。本书适合高等学校信息安全、计算机科学技术和通信工程等专业本科生和研究生使用， 也可供相关领域的科研人员和技术人员参考。

本书由贾春福、钟安鸣、赵源超等编写， 最后由贾春福统稿。李瑞琪、郑万通、王小璐、董奇颖、陈孟琪、李士佳、田美琦等对书中的内容进行了校对， 在此表示感谢。另外，本书是南开大学教材资助项目， 在此也表示衷心的感谢。

由于时间仓促， 书中难免有疏漏和不当之处， 敬请读者批评指正。

编者

2017 年12 月于南开园

第1 章预备知识  1

1.1集合、 关系和函数  1

1.1.1集合  1

1.1.2关系  6

1.1.3函数  13

1.2组合数学初步知识 19

1.2.1排列与组合  19

1.2.2生成函数 26

习题  33

第2 章数论基础（一）  35

2.1整除 35

2.1.1整除与带余除法  35

2.1.2最大公因子与辗转相除法 38

2.1.3连分数  43

2.1.4算术基本定理  50

2.1.5梅森素数和费马素数  53

2.2同余 55

2.2.1同余的概念和性质  55

2.2.2剩余类和欧拉定理  58

2.2.3线性同余方程  63

2.2.4孙子定理与同余方程组  67

2.2.5高次同余方程  74

习题  79

第3 章数论基础（二）  82

3.1原根 82

3.1.1整数的次数  82

3.1.2原根的概念  86

3.1.3指数与 ｎ 次剩余  92

3.2二次剩余 96

3.2.1二次剩余的概念和性质  96

3.2.2勒让德符号与二次互反律  100

3.2.3雅可比符号  106

3.3数论的典型应用  109

3.3.1素性检验算法  109

3.3.2因子分解算法  115

习题 117

第4 章代数系统基础  119

4.1群  119

4.1.1群及其基本性质 119

4.1.2子群  123

4.1.3循环群和群的生成 125

4.1.4陪集和拉格朗日定理  128

4.1.5同态与同构  130

4.1.6正规子群与商群 134

4.1.7循环群的分类  137

4.1.8置换群  138

4.2交换环和域  141

4.2.1交换环及其基本性质  141

4.2.2域及其基本性质 147

4.2.3同态与同构  148

4.2.4一元多项式环  150

4.2.5理想和商环  151

4.3域上的一元多项式环  156

4.3.1一元多项式的整除 157

4.3.2一元多项式环的理想  160

4.3.3域上一元多项式唯一分解定理  161

4.3.4多项式不可约性检验  162

4.3.5一元多项式的同余与商环  164

4.4有限域理论初步  165

习题 169

第5 章椭圆曲线  171

5.1椭圆曲线的预备知识  171

5.1.1仿射平面和射影平面  171

5.1.2判别式、 结式和代数不变量  173

5.1.3一元三次方程的公式解———Cartan 公式  177

5.2椭圆曲线的概念  178

5.2.1Weierstrass 方程  178

5.2.2椭圆曲线方程  181

5.2.3椭圆曲线上点的加法群（Mordell Weil 群）  182

5.2.4有限域上的椭圆曲线  187

5.3离散对数初步  191

5.3.1有限域上的离散对数  191

5.3.2椭圆曲线上的离散对数  193

习题 194

第6 章线性反馈移位寄存器  196

6.1反馈移位寄存器  196

6.1.1反馈移位寄存器简介  196

6.1.2线性反馈移位寄存器简介  197

6.1.3非线性组合移位寄存器简介  198

6.2分圆多项式和本原多项式  198

6.2.1分圆多项式  198

6.2.2本原多项式  202

6.3 M 序列  205

6.3.1 LFSR 的特征多项式  205

6.3.2 m 序列的产生条件 207

6.3.3 m 序列的特点  208

6.3.4 m 序列的破译  210

习题 212

参考文献 213

在互联网科技高度发展的今天，信息安全越来越受到重视。作为信息安全专业本科的专业基础教材，本书系统地介绍了信息安全领域涉及的数学基础知识，内容全面，论证清晰，对信息安全理论和技术的深入学习具有重要的意义。

贾春福，男，博士后，南开大学信息技术科学院计算机科学与信息安全系副主任。主要研究领域涉及计算机网络与信息安全、可信计算、恶意代码分析和软件安全等领域。先后主持或参加国家攀登计划项目、国家“973”计划项目、“863”计划项目和国家自然科学基金项目8项；省部级科研项目等9项；获天津市自然科学二等奖1项。发表研究论文近百篇，其中70余篇分别被SCI和EI收录，100余篇次被国内、国际专著或论文引用。